登入
首頁 所有文章 資料結構 圖形結構-基本介紹與表示方法
長也   2018-12-05 10:53:02(11個月前)    222點閱   0喜歡  0收藏
圖形結構-基本介紹與表示方法  

圖形結構的專有名詞

G1 G2

 

  1. 頂點(Vertex):上兩張圖之圓圈

  2. 邊(EDGE):每個頂點之間的連線

  3. 無向圖(undirected graph):邊不具有方向者(即沒有箭頭),例如上圖的G1

  4. 有向圖(directed graph):邊具有方向性(即有箭頭),例如上圖的G2

  5. 圖形(graph):由所有頂點與邊所組合的集合,以G=(V,E)表示。無向圖當中,(v1, v2)和(v2, v1)表示相同的邊,但在有向圖當中<v1, v2> 和 <v2, v1>是不同的邊。其中,通常以"()"表示無向的邊,以"<>"表示有向的邊。

  6. 相鄰(adjacent):無向圖中若存在一邊(v1, v2),我們稱v1與v2相鄰。在有向圖中<v1, v2>,我們稱v1是adjacent to v2 或 v2 是 adjacent from v1。

  7. 子圖(subgraph):若有一圖G'的頂點與邊都包含於G,我們稱G'為G的子圖。例如下列的圖片中為G1的部分子圖:

  8. 路徑(path):由一個邊或一個以上的邊所組成。例如在G3中由頂點1至頂點3所經過的邊。

  9. 循環(cycle):在一路徑上,若頭尾頂點都相同者稱之。例如G2的2, 3, 2。

圖形資料結構的表示方法

相鄰矩陣(adjacency martix)

將圖形中的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。

相鄰串列(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. 圖形的資料結構有兩種表示方法:相鄰矩陣與相鄰串列。

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

本文作者:長也

糾結與想不開的資管系學生,之前常碰PHP,現在常碰到的是Python,閒暇之餘就記錄一些筆記。

             

如要發表回覆,請先 登入

  0則回覆