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

A. 有一棵或多棵 B. 只有一棵 C. 一定有多棵 D. 可能不存在

[tag_link]

正确答案：A

结论

选 A。无向连通图至少存在一棵最小生成树，但权值相同时可能存在多棵。

推导

连通图可通过不断选取不成环的边得到生成树，有限棵生成树中总权值最小者即为 MST；若不同边组合具有相同最小代价，MST 不唯一。

易错点

连通性保证存在性，不保证唯一性；D 把“可能不唯一”误解成“可能不存在”。