题目
如何判断一个图是否是连着的?图论,算法
连着的(connected)就是从任意一个顶点vi到vj之间存在一条路线.表达不好请见谅.
求算法,我是学计算机的,目前这个作业要求写出一个算法判断一个图是否完整(连着),
连着的(connected)就是从任意一个顶点vi到vj之间存在一条路线.表达不好请见谅.
求算法,我是学计算机的,目前这个作业要求写出一个算法判断一个图是否完整(连着),
提问时间:2021-02-02
答案
连通图的特点是图中任意两点都是连通的,也就是说只要从任意一点出发能够到达所有的点就能够证明是连通图,否则就是不连通图
因为不知道你准备采用什么,具体算法我就不写语言了,只是解释一下原理:
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数量,如果少了则不是连通图
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
最新试题
热门考点
- 1上海东方明珠电视塔是亚洲最高的电视塔,它的高度是468米.小明家住的楼房有12层,比东方明珠电视塔矮12分之11.这幢12层住宅楼的高度是多少米?
- 210.4保留一位有效数字是几
- 3一个什么的微笑的200字作文
- 4saw Mika`s mv on television 翻译
- 5Mr.White is working now.(同义句) Mr.White is_____ _____now
- 6直四棱柱是直平行六面体,为什么
- 7句子都有什么描写方法
- 8That is difficulty to define new target in my life.maybe i need change my current peaceful life.anyw
- 9已知-5b(2n+1)a(m)与3a(2m-3)b(n+3)是同类项,则m=______,n=______
- 10阿托品 新福林 毒扁豆碱 和毛果芸香碱对瞳孔的作用,说明它们的作用机理有什么差别