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

《采用邻接表存储结构,编写一个求无向图的连通分量个数的算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学院名称专业班级实验成绩学生姓名学号实验日期课程名称数据结构实验题目3图一、实验目的与要求熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。二、主要仪器设备Cfree三、实验内容和原理[问题描述]采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。[输入]图顶点的个数，和以各个顶点为弧尾的所有弧，并以-1结束输入。[输出]连通分量的个数。[存储结构]图采用邻接矩阵的方式存储。[算法的基本思想]用到深度优先搜索，先从任意一个顶点开始进行深度优先搜索，搜索完后，连通分量个数增1。然后再从没有遍历

2、过的顶点找一个出来进行深度优先搜索，搜索完后，连通分量个数增1。一直到所有的顶点都被遍历过。[参考源程序]#include#includeintn;structVNode{//顶点intposition;structVNode*next;};structArcNode{//弧intmark;structVNode*first;};voidDFS(structArcNode*v,structArcNode*w){//深度优先搜索structVNode*L;w->mark=1;L=w->fir

3、st;while(L!=NULL){if((v+(L->position))->mark==0){DFS(v,(v+L->position));//递归调用}L=L->next;}}intmain(){inti,j,k;intnum=0;structArcNode*p;structVNode*temp;structVNode*flag;printf("请输入顶点个数n：");scanf("%d",&n);while(n<1){printf("你输入的值不合理，请重新输入：");scanf("%d",&n);}p=(st

4、ructArcNode*)malloc(n*sizeof(structArcNode));/*说明：1.Vi表示第i个顶点，它在表中的位置为i-1，如V3在表中的位置为2;2.如果输入以V1为弧尾的所有弧(假设存在弧和)则输入：21-1(只需输入弧头的位置，并用-1表示结束)*/for(i=0;i

5、t=NULL;}else{temp=(structVNode*)malloc(sizeof(structVNode));temp->position=k;temp->next=NULL;p[i].first=temp;p[i].mark=0;flag=temp;scanf("%d",&k);while(k!=-1){temp=(structVNode*)malloc(sizeof(structVNode));temp->position=k;temp->next=NULL;flag->next=temp;flag=temp;s

6、canf("%d",&k);}}}i=0;while(p[i].mark==0){//计算连通分量的个数DFS(p,(p+i));num++;i=0;while(p[i].mark!=0&&i

7、有的顶点都被遍历过。实验结果如图:六、实验心得及体会通过本次实验，我更好的掌握了图的相关操作，能够熟练的进行图的建立、遍历。在编写程序时，有很多不明白的地方，在得到同学的鼎立相助后，基本解决了这些问题。