![]() |
![]() |
G1 | G2 |
將圖形中的n個頂點以n*n的矩陣表示,以V(i,j)表示。若V(i,j)!=0時,代表vi與vj有一條邊為(vi,vj),而有向圖則表示有一邊<Vi, Vj>。若V(i, j) == 0時,表示頂點i與頂點j沒有邊存在(有一些書會將頂點自己的邊設為無限大)。
以下使用相鄰矩陣來表示上圖的G1與G2:
i / j | 1 | 2 | 3 | 4 |
1 | 0 | 1 | 1 | 1 |
2 | 1 | 0 | 1 | 1 |
3 | 1 | 1 | 0 | 1 |
4 | 1 | 1 | 1 | 0 |
G1 |
i / j | 1 | 2 | 3 |
1 | 0 | 1 | 0 |
2 | 0 | 0 | 1 |
3 | 0 | 1 | 0 |
G2 |
我們可以發現,以直行為i(起點),以橫列為j(終點),而相鄰矩陣是對稱的,其對角線都是0。
相鄰串列是將所有的頂點V都作為串列首,而串列首後的節點表示串列首與該節點有一邊存在。以下以相鄰串列來表示上圖G1與G2。
(G1)
由上圖可知由頂點1出發到達其他點的邊有(1,2)、(1,3)、(1,4),頂點2出發的邊有(2,1)、(2,3)......,由頂點4出發的邊有(4,1)、(4,2)、(4,3)。
(G2)
由上圖可知由頂點1出發的邊有(1,2),由頂點2出發的邊有(2,3),由頂點3出發的邊有(3,2)。
了解如何建立圖形之後,下一篇文章討論如何走訪已經建立好的圖形。
關於作者
粉絲專頁
文章分類