求一个无向图G的连通分量的个数.doc

《求一个无向图G的连通分量的个数.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》实验报告实验内容：（一）判断一个图有无回路（二）求一个无向图G的连通分量的个数一、目的和要求（需求分析）：1、了解图的定义和图的存储结构。2、熟悉掌握图的邻接矩阵和邻接表。3、理解图的遍历算法---深度优先搜索和广度优先搜索。4、学会编程处理图的连通性问题。二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）判断一个图有无回路：在程序设计中，先必须确定所要创建的图是有向还是无向，是图还是网，其次再根据各自的特点，用连接表来实现创建。在有向图中，先找出入度为0的顶点，删除与这个顶点相关联的边（出边），将与这些边相

2、关的其它顶点的入度减1，循环直到没有入度为0的顶点。如果此时还有未被删除的顶点，则必然存在环路，否则不存在回路。无向图则可以转化为：如果存在回路，则必然存在一个子图，是一个回路。因此回路中所有定点的度>=2。第一步：删除所有度<=1的顶点及相关边，并将另外与这些边相关的其它顶点的度减1。第二步：将度数变为1的顶点排入队列，并从该队列中（使用栈）取出一个顶点，并重复步骤一。如果最后还有未删除的顶点，则存在回路，否则没有。求一个无向图G的连通分量的个数：用连接表创建图，对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰

3、为其各个连通分量中的顶点集。所以在设计中，为了统计出无向图中的连通分量个数，则因在其深度优先所搜无向图时对函数DFSTraverse(ALGraphG)调用DFS次数进行统计，其结果便为无向图中连通分量个数。三、调试和运行程序过程中产生的问题及采取的措施：在调试和运行求一个无向图G的连通分量的个数程序时，由于执行语句块voidDFSTraverse(ALGraphG)先于voidDFS(ALGraphG,intv)，而voidDFSTraverse(ALGraphG)内调用了DFS()，因此计算机无法正确运行，将两者顺序进行了交换，程序便实现了其功能，且运行正常。四、

4、源程序及注释：判断一个图有无回路：#include#include#include//输出有向图的一个拓扑序列。//图的邻接表存储表示#defineMAX_NAME3//顶点字符串的最大长度+1#defineMAX_VERTEX_NUM20#defineSTACK_INIT_SIZE10//存储空间初始分配量#defineSTACKINCREMENT2//存储空间分配增量typedefintInfoType;//存放网的权值typedefcharVertexType[MAX_NAME];//字符串类型typed

5、efenum{DG,DN,AG,AN}GraphKind;//{有向图,有向网,无向图,无向网}typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//网的权值指针）}ArcNode;//表结点typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//第一个表结点的地址,指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];//头结点typed

6、efstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。intLocateVex(ALGraphG,VertexTypeu){inti;for(i=0;i

7、inti,j,k;intw;//权值VertexTypeva,vb;ArcNode*p;printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3):");scanf("%d",&(*G).kind);printf("请输入图的顶点数和边数:（空格）");scanf("%d%d",&(*G).vexnum,&(*G).arcnum);printf("请输入%d个顶点的值(小于%d个字符):",(*G).vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;++i)//构造顶点向量{scanf("%s