1、任何一個帶權無向連通圖的最小生成樹——可能是不唯一的。

2、給定有權無向圖的鄰接矩陣如下，其最小生成樹的總權重是：14

3、給定有權無向圖如下。關于其最小生成樹，最小生成樹不唯一，其總權重為23。

4、給出如下圖所示的具有 7 個結點的網 G，采用Prim算法，從4號結點開始，給出該網的最小生成樹。樹結點收集順序是4563201.

5、已知無向圖 G 如下所示，使用克魯斯卡爾（Kruskal）算法求圖 G 的最小生成樹，加入到最小生成樹中的邊依次是：(b,f), (b,d), (a,e), (c,e), (b,e)

6、無向連通圖的最小生成樹有一個或多個。

7、若一個無向連通圖沒有權值相同的邊，則該無向圖的最小生成樹唯一。

8、在求最小生成樹時，Kruskal算法更適合于稀疏圖。

9、給定下圖，其最小生成樹的總權重是30.

10、適合構造一個稠密圖G的最小生成樹Prime算法。

11、在圖采用鄰接表存儲時，求最小生成樹的 Prim 算法的時間復雜度為O(n+e)。

12、給定有權無向圖的鄰接矩陣如下，其最小生成樹的總權重是：23.

13、任何一個無向連通圖的最小生成樹有一顆或者是多顆。

14、在求最小生成樹時，Prim算法更適合于稠密圖。

15、用DFS遍歷一個無環有向圖，并在DFS算法退棧返回時打印相應的頂點，則輸出的頂點序列是逆拓撲有序序列。

16、如果從無向圖的任一頂點出發進行一次深度優先搜索可訪問所有頂點，則該圖一定是連通圖。

17、給定一有向圖的鄰接表如下。從頂點V1出發按深度優先搜索法進行遍歷，則得到的一種頂點序列為：V1,V5,V4,V7,V6,V3,V2

18、在圖中自c點開始進行廣度優先遍歷算法可能得到的結果為：c,f,a,d,e,b。

19、給定一有向圖的鄰接表如下。若從v1開始利用此鄰接表做廣度優先搜索得到的頂點序列為：{v1, v3, v2, v4, v5}，則該鄰接表中順序填空的結果應為：v3, v2, v4。

20、給定有權無向圖的鄰接矩陣如下，其最小生成樹的總權重是：8.

21、用于求解最小生成樹的是Prime算法。

22、克魯斯卡爾（Kruskal）算法：

• 假設連通圖G=(V,E)，其中V是頂點集，E是邊集。初始時，最小生成樹T=(V′,E′)，V′為圖G中所有頂點的集合，E′為空集。
• 從E中選取權值最小的邊，若將該邊加入E′中不會形成回路，則將其加入E′；否則，舍棄該邊。
• 重復上述步驟，直到E′中的邊數為n?1或者所有邊都已考察過為止，其中n是圖G中頂點的個數。此時T=(V′,E′)就是圖G的一棵最小生成樹。

23、Prime算法?：

• 從圖中任意選擇一個起始頂點v0?，將其加入到最小生成樹的頂點集合U中。
• 不斷從與U中頂點相鄰的邊中選擇權值最小的邊，將該邊及其對應的另一個頂點加入到U中，直到所有頂點都被加入到U中。