算法设计与分析书中程序(第章)

《算法设计与分析书中程序(第章)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、【程序4-1】ENode类enumColorType{White,Gray,Black};structENode{intadjVex;ENode*nextArc;};classGraph{public:Graph(intmSize){//构造仅有n个结点的图的邻接表n=mSize;a=newENode*[n];for(inti=0;i

2、l(int*prarent);//一维数组parent保存BFS生成森林Mprotected:voidDFS(intu,int*parent,ColorType*color);//递归DFS函数访问从u可达结点voidBFS(intu,int*parent,ColorType*color);//BFS函数访问从u可达结点MENode**a;//生成指向ENode类对象的指针数组intn;//图中结点数目};【程序4-2】图的广度优先遍历voidGraph::BFS_Traversal(int*pare

3、nt){//遍历算法将在parent数组中返回以双亲表示法表示的BFS生成森林ColorType*color=newColorType[n];//颜色数组cout<

4、aph::BFS(intu,int*parent,ColorType*color){//广度优先搜索算法Queueq(QSize);color[u]=Gray;cout<<""<nextArc){//检测E-结点u的全部邻接点intv=w->adjVex

5、;if(color[v]==White){color[v]=Gray;cout<<""<

6、w->nextArc){intv=w->adjVex;if(color[v]==White){parent[v]=u;DFS(v,parent,color);}}color[u]=Black;f[u]=time++;//记录第2个时间}【程序4-4】计算d和LowvoidGraph::DFS(intu,intp){//u是起始结点，p是u的双亲结点Low[u]=d[u]=time++;//Low[u]=d[u]for(ENode*w=a[u];w;w=w->nextArc){·159·intv=w->

7、adjVex;if(d[v]==-1){//表示v尚未访问DFS(v,u);if(Low[u]>Low[v])Low[u]=Low[v];//是树边}elseif(v！=p&&Low[u]>d[v])Low[u]=d[v]//是反向边}}【程序4-5】求双连通分量voidGraph::BiCom(intu,intp){Low[u]=d[u]=time++;eNodee;for(ENode*w=a[u];w;w=w->nextArc){intv=w->adjVex;e.u=u;e.v

8、=v;if(v！=p&&d[v]=d[u]){cout<e.v)Swap(e.u,e.v);elseif(u>v&&e.u