大师作文网如何判断一个图是否是连着的?图论,算法
来源：学生作业帮 编辑：大师作文网作业帮 分类：数学作业 时间：2024/11/14 09:04:54
如何判断一个图是否是连着的?图论,算法
连着的(connected)就是从任意一个顶点vi到vj之间存在一条路线.表达不好请见谅.
求算法,我是学计算机的,目前这个作业要求写出一个算法判断一个图是否完整（连着）,
连着的(connected)就是从任意一个顶点vi到vj之间存在一条路线.表达不好请见谅.
求算法,我是学计算机的,目前这个作业要求写出一个算法判断一个图是否完整（连着）,
连通图的特点是图中任意两点都是连通的,也就是说只要从任意一点出发能够到达所有的点就能够证明是连通图,否则就是不连通图
因为不知道你准备采用什么,具体算法我就不写语言了,只是解释一下原理：
1 采用数组、链表或数组,先将所有顶点定义在数组POINT中.
2 采用二维数组,将所有边（线段）定义在二维数组LINE中,记录两遍,边的两个顶点分别作为第一项如（v0,v3）(v3,v0).
3 取出一个顶点v0加入到新数组CONPOINT中,并在顶点数组POINT中删除.
4 while循环,停止条件是CONPOINT中都标记着已读
{
从CONPOINT中取出一个有未读标记的顶点X,并作已读标记.
从二维数组LINE中查找第一项中包含X的边,将选出边的第二个顶点（1个或多个）取出,并加入到新数组CONPOINT中,并作未读标记（如果已有该点则不作插入）
将选出的边从二维数组LINE中删除.
}
比较CONPOINT和POINT数量,如果少了则不是连通图
因为不知道你准备采用什么,具体算法我就不写语言了,只是解释一下原理：
1 采用数组、链表或数组,先将所有顶点定义在数组POINT中.
2 采用二维数组,将所有边（线段）定义在二维数组LINE中,记录两遍,边的两个顶点分别作为第一项如（v0,v3）(v3,v0).
3 取出一个顶点v0加入到新数组CONPOINT中,并在顶点数组POINT中删除.
4 while循环,停止条件是CONPOINT中都标记着已读
{
从CONPOINT中取出一个有未读标记的顶点X,并作已读标记.
从二维数组LINE中查找第一项中包含X的边,将选出边的第二个顶点（1个或多个）取出,并加入到新数组CONPOINT中,并作未读标记（如果已有该点则不作插入）
将选出的边从二维数组LINE中删除.
}
比较CONPOINT和POINT数量,如果少了则不是连通图