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

本文格式为Word版，下载可任意编辑——采用邻接表存储结构，编写一个求无向图的连通分量个数的算法

学院名称学生姓名课程名称数据结构专业班级学号试验题目3图试验成绩试验日期一、试验目的与要求熟悉图的存储结构，把握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。二、主要仪器设备Cfree三、试验内容和原理[问题描述]采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。[输入]图顶点的个数，和以各个顶点为弧尾的所有弧，并以-1终止输入。[输出]连通分量的个数。[存储结构]图采用邻接矩阵的方式存储。[算法的基本思想]用到深度优先探寻，先从任意一个顶点开始进行深度优先探寻，探寻完后，连通分量个数增1。然后再从没有遍历过的顶点找一个出来进行深度优先探寻，探寻完后，连通分量个数增1。一直到所有的顶点都被遍历过。[参考源程序]#include#includeintn;structVNode{//顶点intposition;structVNode*next;};structArcNode{//弧intmark;structVNode*first;};voidDFS(structArcNode*v,structArcNode*w){//深度优先探寻structVNode*L;w->mark=1;L=w->first;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(\while(n和)则输入：21-1(只需输入弧头的位置，并用-1表示终止)*/for(i=0;iposition=k;temp->next=NULL;p[i].first=temp;p[i].mark=0;flag=temp;scanf(\while(k!=-1){temp=(structVNode*)malloc(sizeof(structVNode));temp->position=k;temp->next=NULL;flag->next=temp;flag=temp;scanf(\}}}i=0;while(p[i].mark==0){//计算连通分量的个数DFS(p,(p+i));num++;i=0;while(p[i].mark!=0}}printf(\此图的连通分量个数为：%d\\n\system(\return0;}五、试验结果与分析习题1：这题主要还是用到深度优先探寻，先从任意一个顶点开始进行深度优先探寻，探寻完后，连通分量个数增1。然后再从没有遍历过的顶点找一个出来进行深度优先探寻，探寻完后，连通分量个数增1。一直到所有的顶点都被遍历过。试验结果如图:六、试验心得及体会通过本次试验，我更好的把握了图的相关操作，能够熟练的进行图的建立、遍历