这两天过得浑浑噩噩，斩断乱絮，迎接新的生活。
今日重点，求解最短路径两大宝———迪杰斯特拉&弗洛伊德。
1.p个顶点p条边的连通图中至少有多少个生成树？（B）
A. 2
B. 3
C. 4
D. P
解析：p个顶点的连通图图至少p-1条边，p条边必有一环，环至少有3条边组成，所以生成树至少有排列的C3取1等于3个，最多应该是p个(p个顶点组成的大环，随便去条边都是生成树)
2.(1)求从指定源点到其余各顶点的迪杰斯特拉(Dijkstra)最短路径算法中弧上权不能为负的原因是在实际应用中无意义;(2)利用Dijkstra求每-对不同顶点之间的最短路径的算法时间是O(n3 )(图用邻接矩阵表示);(3
最后
以上就是着急时光最近收集整理的关于图——牛客网刷题第二波的全部内容，更多相关图——牛客网刷题第二波内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复