Embedded Files
Deadline: to be announced 23:30 "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:
Requirement:
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
1.亂數產生圖 G 的相鄰矩陣，其濃密或稀疏程度可調整，使用者可選擇是否要印出 (如提示圖)；
2.利用Kruskal演算法找出G的最小延展樹，印出執行時間，此最小延展樹可讓使用者選定是否要印出；
3.利用Prim演算法找出G的最小延展樹，印出執行時間，此最小延展樹可讓使用者選定是否要印出.
4. Kruskal與Prim的演算法執行時間比較圖檔
Program example
Program example
Generate a undirected graph G=(V, E) with respect to the predefined parameters using random numbers
Find an MST of G by Kruskal's algorithm
Observe the e*3 edge-matrix transformed from the cost matrix of G
Find an MST of G by Prim's algorithm
Find MSTs of various Gs with different densities (e.g., 1, 0.2, 0.01) using different skills (finding min. by loop/heap; cycle-detection by loop/union-find)
Determine which is better for finding MST under what circumstances
Reference
Reference
Google Sites
Report abuse