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

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