主題

ZeroJudge - f668: FJCU_109_Winter_Day1_Lab3 Adjacency Matrix 和 Adjacency List 練習 解題心得

Not In My Back Yard | 2021-02-25 00:00:04 | 巴幣 0 | 人氣 48

題目連結:


題目大意:
輸入第一列給定兩正整數 N 、 M(0 ≦ N ≦ 10,0 ≦ M ≦ N(N - 1) ÷ 2),代表有一個簡單無向圖有 N 個節點(編號為 1 ~ N)、M 條邊。

接著有 M 列輸入,每列給定兩個正整數 s 、 t (1 ≦ s 、t ≦ N),代表節點 s 與節點 t 之間有一條邊。

請按照節點編號由小到大輸出每個節點的相鄰節點(互相之間有直接的邊),格式參見範例輸出。

注:簡單圖為沒有自環(指向自己的邊)和重邊(起點與終點一樣的邊)的圖。



範例輸入:
5 5
1 2
2 3
3 4
5 1
2 4


範例輸出:
1: 2 5
2: 1 3 4
3: 2 4
4: 2 3
5: 1


解題思維:
如題目標題所述,這題就是實作鄰接矩陣(Adjacency Matrix)或是鄰接表(Adjacency List)的題目。



如果是鄰接矩陣,可以單純用一個 N × N 的二維布林陣列 M 表示,其中 M[i][j] 代表節點 i 有邊到節點 j。因為圖為無向圖,所以 M[i][j] 跟 M[j][i] 只會同時為 0 或是同時為 1。所有邊設定完後,就掃過一次矩陣便可以知道每個節點的相鄰節點(而且可以很自然地由小到大)。

如果是鄰接表,通常會使用 vector 這種可變大小的陣列(使用 N 個 vector,代表有 N 個節點),然後對於每對 s 、 t ,將會在 s 的 vector 放入 t 、在 t 的 vector 放入 s 以示兩者是相鄰的。不過輸出的時候,需要先排序每個節點的 vector ,才能保證順序(因為給定順序不固定,不能保證由小到大)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作