任何一个无向连通图的最小生成树（）

查看本题答案

包含此试题的试卷

G’是G的子图 G’是G的连通分量 G’是G的极小连通子图且V=V’ G’是G的一个无环子图

寻找关键路径是关于带权有向图的操作寻找关键路径是关于带权无向图的操作连通图的生成树不一定是唯一的带权无向图的最小生成树不一定是唯一的

带权连通图的某最小生成树的权值之和一定小于其他生成树的权值之和从源点到终点的最短路径是惟一的任意一个AOV网不一定存在拓扑序列任意一个AOE网中的关键路径是惟一的

O（（n+1）²） O（n²） O（n²-1）（n²+1）

O（log₂e） O（log₂e-1） O（elog₂e）以上都不对

求最小生成树求最短路径拓扑排序图的遍历

若网较稠密，则Prim算法更好两个算法得到的最小生成树是一样的 Prim算法比Kruscal算法效率更高 Kruscal算法比Prim算法效率更高

O(log₂e) O(log₂e-1) O(elog₂e) 以上都不对

只有一棵一棵或多棵一定有多棵可能不存在

O((n+1)²) O(n²) O(n²-1) (n²+1)

连通分量是无向图中的极小连通子图生成树是连通图的一个极大连通子图若一个含有n个顶点的有向图是强连通图，则该图中至少有n条弧若一个含有n个顶点的无向图是连通图，则该图中至少有n条边

分治贪心动态规划回溯

连通无向网的最小生成树中，顶点数恰好比边数多1 若有向图是强连通的，则其边数至少是顸点数的2倍可以采用AOV网估算工程的工期关键路径是AOE网中源点至汇点的最短路径

24 25 26 27

G'是G的子图 G'是G的连通分量 G'是G的极小连通子图且V=V' G'是G的一个无环子图