图的算法题1,给定一个不带权值有m条变得连通图G, - 已解决 - 学校大全

图的算法题1,给定一个不带权值有m条变得连通图G,设计一个时间复杂度为O(m)的算法构造图G的一棵生成树.2,试写出DF

图的算法题

1,给定一个不带权值有m条变得连通图G,设计一个时间复杂度为O(m)的算法构造图G的一棵生成树.

2,试写出DFS生成树（或生成森林）的算法,要求打印出所有的边.

3,给定图G(V,E),设计算法统计图G中连通块的个数.

收藏：

0

点赞数：

0

评论数：

0

1个回答

这几个都是很经典的题目,书上或百度上可以找到答案的,没太大难度吧.第一第二问都要用到一个并查集的概念,就是用来查询两个点是否属于同一个集合.第三问就是对于无向图一次DFS可搞定,对于有向图得两次DFS可搞定（查一下强连通的概念即可找到很多资料）

点赞数：

0

评论数：

0

相关问题

设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．

点赞数：
0
回答数：
1
数据结构：假设图G采用邻接表存储,试设计一个算法,求不带权无向连通图G中距离顶点v的最远的顶点?

点赞数：
0
回答数：
1
数据结构,选什么,下面（　）算法适合构造一个稠密图G的最小生成树.A． Prim算法 B．Kruskal算法 C．Flo

点赞数：
0
回答数：
1
图论题,设G是有p顶点的图,δ(G)>=((p+k)-1)/2,试证：G是k-连通的.

点赞数：
0
回答数：
1
设连通无向图G采用邻接表表示.写出求最小生成树Prim算法的实现代码.

点赞数：
0
回答数：
1
从顶点A出发,写出按普利姆算法构造下图的一棵最小生成树的过程.

点赞数：
0
回答数：
1
有关平面图的问题设G为任意的连通平面图,则有n-m+r=( )；若G是简单连通平面图n>=3,则m<=(

点赞数：
0
回答数：
1
对于含有n个顶点e条边的无向图,求最小生成树的Kruskal算法的时间复杂度为（）.

点赞数：
0
回答数：
1
13.用Prim算法和Kruskal算法构造图的最小生成树,所得到的最小生成树是否相同?

点赞数：
0
回答数：
1
请对下图的无向带权图：1写出它的邻接矩阵,并按普里姆算法求其最小生成树；

点赞数：
0
回答数：
1

关注公众号

一起学习，一起涨知识

最新问答：实数a在数轴上的位置如图,化简绝对值a-1+根号(a-2)的2次方的值一个正方体体积是22.5立方米,一个圆锥的底面半径和高都等于该正方体的棱长.这个圆锥的体积是多少? 9个数字按顺时针次序为1、9、3、4、2、6、8、5、7、排成一个圈,在某两个数字之间剪开.分别按顺时针和逆时针次序形成 Before you____the design of this product,you need to study t the production possibilities frontier (2009.济南模拟).先化简,再求值: Miss wang often teaches her American friends ___(cook) Chine 39-77除以11等于多少今年一季度，我市因治霾成效显著获得省治霾奖励。PM2.5是造成雾霾天气的元凶之一，下列行为不会增加大气中PM2.5的是（春种一粒粟秋收万颗子怎么念（2014•盐城三模）凋亡抑制蛋白与肿瘤的发生、发展有关，科学家利用先天无胸腺的裸鼠，探究凋亡抑制蛋白基因的反义脱氧核苷伴随着“环保低碳、节能减排”的生活新理念，太阳能汽车营运而生．这款汽车利用太阳能电池板将太阳能转化为电能，再利用电动机为省略乘号怎么写5x(m+n)= 如何证明园包围椭圆范仲淹的《渔家傲秋思》中抒发征夫戍边的无奈和对家乡的眷恋之情的句子是晚什么朝什么四词语英语翻译长城全长8851.8千米,高六至七米,宽四至五米下列关于摩擦力的说法，正确的是（　　）补全对话lucy：excuse me,mike.( )the time?mike:( ),i don't( )a wat 函数f(x)=3sinx+5sin(x+pi/3)的最大值是

热门专题：老师生活解答年级英文答案溶液面积反应保留叙述功率计算运动分子阅读作文成语曲线跪求

全站推荐：稼穑名言喧泄近义词孩儿面造句晓敏段落生故事性气造句云车造句难友造句学习紧张段落农夫和蛇递补造句诚信教育条幅复函造句动物名成长的足印念往昔句子没睡好句子班干部竞选稿爱森林句子收获满满造句