2022年采用邻接表存储结构,编写一个求无向图的连通分量个数的算法 .pdf

学院名称专业班级实验成绩学生姓名学号实验日期课程名称数据结构实验题目3 图一、实验目的与要求熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。二、主要仪器设备Cfree 三、实验内容和原理问题描述 采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。输入 图顶点的个数，和以各个顶点为弧尾的所有弧，并以-1 结束输入。输出 连通分量的个数。存储结构 图采用邻接矩阵的方式存储。算法的基本思想用到深度优先搜索，先从任意一个顶点开始进行深度优先搜索，搜索完后，连通分量个数增1。然后再从没有遍历过的顶点找一个出来进行深度优先搜索，搜索完后，连通分量个数增1。一直到所有的顶点都被遍历过。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 参考源程序 #include #include int n; struct VNode /顶点int position; struct VNode* next; ; struct ArcNode /弧int mark; struct VNode* first; ; void DFS(struct ArcNode* v,struct ArcNode* w) / 深度优先搜索struct VNode* L; w-mark=1; L=w-first; while(L!=NULL) if(v+(L-position)-mark=0) DFS(v,(v+L-position); /递归调用 L=L-next; int main() int i,j,k; int num=0; struct ArcNode* p; struct VNode* temp; struct VNode* flag; printf(n 请输入顶点个数n：); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - scanf(%d,&n); while(n1) printf( 你输入的值不合理，请重新输入：n); scanf(%d,&n); p=(struct ArcNode*)malloc(n*sizeof(struct ArcNode); /*说明： 1.Vi 表示第 i 个顶点，它在表中的位置为i-1，如 V3 在表中的位置为2; 2.如果输入以V1 为弧尾的所有弧(假设存在弧 和) 则输入： 2 1 -1( 只需输入弧头的位置，并用-1 表示结束 )*/ for(i=0;iposition=k; temp-next=NULL; pi.first=temp; pi.mark=0; flag=temp; scanf(%d,&k); while(k!=-1) temp=(struct VNode*)malloc(sizeof(struct VNode); temp-position=k; temp-next=NULL; flag-next=temp; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - flag=temp; scanf(%d,&k); i=0; while(pi.mark=0) /计算连通分量的个数DFS(p,(p+i); num+; i=0; while(pi.mark!=0&in) i+; printf( 此图的连通分量个数为：%dn,num); system(pause); return 0; 五、实验结果与分析习题 1：这题主要还是用到深度优先搜索，先从任意一个顶点开始进行深度优先搜索，搜索完后，连通分量个数增1。然后再从没有遍历过的顶点找一个出来进行深度优先搜索，搜索完后，连通分量个数增1。一直到所有的顶点都被遍历过。实验结果如图 :名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 六、实验心得及体会通过本次实验，我更好的掌握了图的相关操作，能够熟练的进行图的建立、遍历。在编写程序时，有很多不明白的地方，在得到同学的鼎立相助后，基本解决了这些问题。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -