國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

四、用 G = (V, E) 表示一個無方向性圖形，其中 V 是點的集合，E 是一組節點(Vertices) 形成邊及對應權重 (Weights) 所組成的集合。今有一圖形 G = (V, E)，V = {0, 1, 2, 3, 4, 5}，圖形的邊與權重值以如下的定義儲存對應連接矩陣 (Adjacency matrix) 表示中的值

    #define MAX_EDGES 100

    typedef struct {

        int col;

        int row;

        int weight;

    } edge;

    edge a[MAX_EDGES];

    已知陣列 a 儲存對應連接矩陣相連接邊的內容如下：a = {(3, 0, 2), (4, 0, 1), (5, 0, 20), (2, 1, 7), (5, 1, 24), (3, 2, 15), (4, 2, 10), (5, 2, 25), (4, 3, 3)}。請畫出陣列 a 所儲存的圖形，然後，利用 Prim 演算法從節點0開始依加入其它節點的順序，畫出此圖之最小擴張樹 (Minimum spanning tree)，並計算其最低權重或成本值。（25分）

0

1

2

3

4

5

0

0

∞

∞

2

1

20

1

∞

0

7

∞

∞

24

2

∞

7

0

15

10

25

3

2

∞

15

0

3

∞

4

1

∞

10

3

0

∞

5

20

24

25

∞

∞

0