(一)九度上一个练习题
-
给定一個无向图和其中的所有边判断这个图是否所有顶点都是连通的。
-
每组数据的第一行是两个整数 n 和 m(0<=n<=1000)n 表示图的顶点数目,m 表示图中边嘚数目如果 n 为 0 表示输入结束。随后有 m 行数据每行有两个值 x 和 y(0<x, y <=n),表示顶点 x 和 y 相连顶点的编号从 1 开始计算。输入不保证这些边是否偅复
-
对于每组输入数据,如果所有顶点都是连通的输出"YES",否则输出"NO"
(二)判断图是否是连通的,可以通过深度优先遍历什么意思的方法判断具体实现为:在图中选定任一一个顶点,对该顶点进行深度优先遍历什么意思如果在这个遍历什么意思过程中所有的顶点都被遍历什么意思到,则该图为连通;反之若存在没有被遍历什么意思到的顶点,则说明该图是非连通的实现代码如下(针对无向图,使用邻接表结构):
int adjvex;//弧指向的节点的值(点的标号) //检测要输入的边是否已经存在针对无向图 //创建图,vexNum代表顶点的个数arcNum代表边的个数,isUnDirected代表的是 是否是无向图 //输入边的顶点和尾点 //还需要检验边是否已经存在这里没有检验 //还需要检验边是否已经存在,这里没有检验 //对第vex個顶点递归的做深度优先遍历什么意思, 若遍历什么意思到该顶点则将visit数组中对应的值置为true //检测图是否是连通的