08. Minimum Cost Spanning Tree: Kruskal's and Prim's algorithms

Finding the minimal spanning tree of a given graph using Kruskal's and Prim's algorithms.

用 Kruskal 和 Prim 演算法，求解給定圖的最小延展樹。

輸入：圖 G=(V, E) 和圖中各邊的權重 (成本距離...)

輸出：G 的 minimal spanning tree 或 "G 無 spanning tree"

需求功能:

1.亂數產生圖 G 的相鄰矩陣，其濃密或稀疏程度可調整，使用者可選擇是否要印出 (如提示圖)；

2.利用Kruskal演算法找出G的最小延展樹，印出執行時間，此最小延展樹可讓使用者選定是否要印出；

3.利用Prim演算法找出G的最小延展樹，印出執行時間，此最小延展樹可讓使用者選定是否要印出。

提示：[有解的例子；相鄰矩陣和求得的 MST 可印出]

[無解的例子]

作業繳交項目：

(a) 程式專案；

(b) Kruskal與Prim的演算法執行時間比較圖檔 (橫軸為點數, 縱軸為求得 MST 所需的時間)

把這兩個演算法執行的"圖上點數"和"時間"（依不同的圖上邊比例，至少三種，），登錄在 excel 上作圖（直條圖、折線圖、...皆可）

分別用以下三種方式測試:

b.1 all w(e)'s > 0 // 即所有邊都存在 ==> G 為完備圖;

b.2 |e|/|all possible edges| <= 1/8 // 令亂數產生的邊小於某值後即設成 無限大; 使邊數 <= (所有最多可能邊數的 1/8); 請看 powercam 的程式做法!!

b.3 |e|/|all possible edges| <= 1/500 // b.2 和 b.3 皆為邊較稀疏的圖

加分項目：

利用Excel 或其它工具作圖表，三種測試方式(b.1、b.2、b.3)

所以需有"三張圖" 每種測試方式各一張 !

[以能凸顯是 Kruskal 較佳或 Prim 較佳為原則 ==> 見下二圖] 圖上邊比例該取多少，可能因各位電腦配備的不同，答案因而不同；以能凸顯是 Kruskal 較佳或 Prim 較佳為原則！

繳交期限:

遲交依照規定扣分, 遲交三天以上不計分。

程式範例