Bonus MST : Kruskal and Prim Algorithm

Deadline :1/21/2018 23:59 "Read before submission"

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

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

Input : a graph G=(V,E) and the weight of every edge

Output : minimum spanning tree of graph G or "No spanning tree"

Requirement:

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

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

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

4. Kruskal與Prim的演算法執行時間比較圖檔

1.Generate graph G in random and G is represented by matrix. The density of graph can be adjusted.

2.Use Kruskal's algorithm to find minimum spanning tree and print the execution time.

3.Use Prim's algorithm to find minimum spanning tree and print the execution time.

4.Comparison chart of the execution time of two MST algorithm

Program example

Reference

https://sites.google.com/site/sjdsifm/ProgrammingAssignment/08-minimum-cost-spanning-tree-kruskal-s-and-prim-s-algorithms