我是靠谱客的博主 着急时光,这篇文章主要介绍图——牛客网刷题第二波,现在分享给大家,希望可以做个参考。

这两天过得浑浑噩噩,斩断乱絮,迎接新的生活。

今日重点,求解最短路径两大宝———迪杰斯特拉&弗洛伊德。

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

最后

以上就是着急时光最近收集整理的关于图——牛客网刷题第二波的全部内容,更多相关图——牛客网刷题第二波内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(47)

评论列表共有 0 条评论

立即
投稿
返回
顶部