#include <stdio.h> #include <stdlib.h> #define MVNum 100 int visited[MVNum]; typedef struct{ char vexs[MVNum]; //顶点向量 int arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //顶点数,边数 }AMGraph; int DFS(AMGraph G, int v);//以v为起点遍历图G(v所在的连通分量) int DFSTraverse(AMGraph G);//遍历图G int LocateVex(AMGraph G,char u) //查询顶点u的下标 { int i,count; for(i=0;i<G.vexnum;++i) if( u==G.vexs[i] ) return i; return -1; } void CreateUDG(AMGraph &G){ int i=0,j,count; char v1,v2; v1=getchar(); while(v1!='#') { G.vexs[i]=v1; i++; v1=getchar(); } G.vexnum=i; for(i = 0; i< G.vexnum;++i) //初始化邻接矩阵,所有元素均为0 for(j = 0; j< G.vexnum;++j) G.arcs[i][j] = 0; scanf("\n%c %c",&v1,&v2); while(v1!='#'&& v2!='#') { i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[i][j] = 1; G.arcs[j][i] = 1; scanf("\n%c %c",&v1,&v2); } } int main(){ AMGraph G; CreateUDG(G); printf("%d",DFSTraverse(G)); return 0; } /* 请在这里填写答案 */
时间: 2024-03-15 18:42:46 浏览: 44
SeqList.h #include <stdio.h> //包含标准输入输出流的头文件 #include <assert.h
这段代码实现了一个无向图的深度优先遍历,并输出遍历的连通分量个数。以下是代码的解释和分析:
1. 定义了一个结构体 `AMGraph`,其中包括顶点向量 `vexs` 和邻接矩阵 `arcs`,以及顶点数和边数。
2. `LocateVex` 函数用于查询顶点 `u` 的下标,返回下标值或者 -1 表示查询失败。
3. `CreateUDG` 函数用于创建无向图,先读入顶点向量,然后初始化邻接矩阵,最后根据输入的边信息更新邻接矩阵。
4. `DFS` 函数是深度优先遍历的实现,以顶点 `v` 为起点遍历图 `G`,并将遍历到的顶点标记为已访问。
5. `DFSTraverse` 函数是深度优先遍历的入口函数,用于遍历整个图 `G`,并返回遍历的连通分量个数。
6. `main` 函数创建一个无向图,调用 `DFSTraverse` 函数进行遍历,并输出遍历的连通分量个数。
需要注意的是,这段代码没有考虑连通性,即如果图不连通,可能存在顶点未被遍历到的情况。如果需要考虑连通性,可以在 `DFSTraverse` 函数中添加循环,直到所有顶点都被遍历到为止。另外,代码中的 `visited` 数组没有被使用,可以考虑在遍历过程中使用该数组来标记已访问的顶点。
阅读全文