|
深度优先遍历的递归算法 ()深度优先遍历算法 typedef enum{FALSETRUE}Boolean;//FALSE为TRUE为 Boolean visited[MaxVertexNum]; //访问标志向量是全局量 void DFSTraverse(ALGraph *G) { //深度优先遍历以邻接表表示的图G而以邻接矩阵表示G时算法完全与此相同 int i; for(i=;in;i++) visited[i]=FALSE; //标志向量初始化 for(i=;in;i++) if(!visited[i]) //v i 未访问过 DFS(Gi); //以v i 为源点开始DFS搜索 }//DFSTraverse ()邻接表表示的深度优先搜索算法 void DFS(ALGraph *Gint i){ //以v i 为出发点对邻接表表示的图G进行深度优先搜索 EdgeNode *p; printf(visit vertex%cG>adjlist[i]vertex);//访问顶点v i visited[i]=TRUE; //标记v i 已访问 p=G>adjlist[i]firstedge; //取v i 边表的头指针 while(p){//依次搜索v i 的邻接点v j 这里j=p>adjvex if (!visited[p>adjvex])//若v i 尚未被访问 DFS(Gp>adjvex);//则以V j 为出发点向纵深搜索 p=p>next; //找v i 的下一邻接点 } }//DFS ()邻接矩阵表示的深度优先搜索算法 void DFSM(MGraph *Gint i) { //以vi为出发点对邻接矩阵表示的图G进行DFS搜索设邻接矩阵是l矩阵 int j; printf(visit vertex%cG>vexs[i]);//访问顶点v i visited[i]=TRUE; for(j=;jn;j++) //依次搜索v i 的邻接点 if(G>edges[i][j]==&&!visited[j]) DFSM(Gj)//(v i v j )∈E且v j 未访问过故v j 为新出发点 }//DFSM 注意 遍历操作不会修改图G的内容故上述算法中可将G定义为ALGraph或MGraph类型的参数而不一定要定义为ALGraph和MGraph的 指针类型但基于效率上的考虑选择指针类型的参数为宜 |
