圖形結構－基本介紹與表示方法

圖形結構的專有名詞

G1	G2

1. 頂點(Vertex)：上兩張圖之圓圈
   
   
2. 邊（EDGE）：每個頂點之間的連線
   
   
3. 無向圖（undirected graph）：邊不具有方向者（即沒有箭頭），例如上圖的Ｇ１
   
   
4. 有向圖（directed graph）：邊具有方向性（即有箭頭），例如上圖的Ｇ２
   
   
5. 圖形（graph）：由所有頂點與邊所組合的集合，以Ｇ＝（V,E）表示。無向圖當中，(v1, v2)和(v2, v1)表示相同的邊，但在有向圖當中<v1, v2> 和 <v2, v1>是不同的邊。其中，通常以"()"表示無向的邊，以"<>"表示有向的邊。
   
   
6. 相鄰（adjacent）：無向圖中若存在一邊（v1, v2），我們稱ｖ１與ｖ２相鄰。在有向圖中<v1, v2>，我們稱v1是adjacent to v2 或 v2 是 adjacent from v1。
   
   
7. 子圖（subgraph）：若有一圖G'的頂點與邊都包含於G，我們稱G'為G的子圖。例如下列的圖片中為G1的部分子圖：
   
   
8. 路徑（path）：由一個邊或一個以上的邊所組成。例如在Ｇ３中由頂點１至頂點３所經過的邊。
   
   
9. 循環（cycle）：在一路徑上，若頭尾頂點都相同者稱之。例如Ｇ２的2, 3, 2。

圖形資料結構的表示方法

相鄰矩陣（adjacency martix）

將圖形中的ｎ個頂點以ｎ＊ｎ的矩陣表示，以Ｖ(i,j)表示。若V(i,j)!=0時，代表vi與vj有一條邊為(vi,vj)，而有向圖則表示有一邊<Vi, Vj>。若V(i, j) == 0時，表示頂點i與頂點j沒有邊存在（有一些書會將頂點自己的邊設為無限大）。

以下使用相鄰矩陣來表示上圖的G1與G2：

我們可以發現，以直行為i(起點)，以橫列為j(終點)，而相鄰矩陣是對稱的，其對角線都是0。

相鄰串列(adjancency list)

相鄰串列是將所有的頂點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)。

結論

1. 圖形由頂點(V)與邊(E)組成。
   
   
2. 若邊有箭頭，則稱為有向圖；若沒有箭頭則為無向圖。
   
   
3. 圖形的資料結構有兩種表示方法：相鄰矩陣與相鄰串列。

了解如何建立圖形之後，下一篇文章討論如何走訪已經建立好的圖形。