Graph

Graph

Graph中文翻做「圖」。此處談及的「圖」並不是指圖片或者圖形。「圖」是一種用來記錄關聯、關係的東西。

一張圖由數個點(vertex)以及數條邊(edge)所構成。點與點之間,得以邊相連接,表示這兩點有關聯、關係。

【註:「點(vertex)」亦可改稱「節點(node)」。】

點的大小形狀和線的粗細長短是無所謂的,我們只在乎它們如何連接。只要連接的關係對了,要怎麼畫都行,簡約、雅觀、平易近人即可!

兩點之間也可以有很多條邊,甚至有自己連到自己的邊。兩點之間有很多條邊,代表這兩點有很多項關聯。一個點有自己連到自己的邊,表示自己和自己有項關聯。

Isomorphism / Isomorphic

Isomorphism中文譯作「同形」,Isomorphic中文譯作「同形的」。如果兩張圖的連接方式一模一樣時,則稱做「同形」。

圖上的邊可以是直的,也可以是彎彎曲曲的,也可以是交錯的。不論邊的形狀如何,都不會改變點與點之間的關聯、關係,終究都會是同形的圖。

圖上的點可以任意移動位置。不論點的位置如何,都不會改變點與點之間的關聯、關係,終究都會是同形的圖。

同形的圖擁有相同的資訊,所以不管選擇哪一張圖都是可以的,只要清楚易懂就可以了!

Directed Graph

邊甚至可以擁有方向性,用來表示兩點間的關係是單向的,並非雙向的。無向邊一般都被視為雙向關係,有向邊一般都被視為單向關係。

一張圖若都是沒有方向性的邊,稱做「無向圖」;一張圖若都是有方向性的邊,則稱做「有向圖」。如果圖上有一些邊是單向的,有一些邊是雙向的,那我就不知道那該叫做什麼圖了。

Weighted Graph

圖上的點可以擁有權重,可做其他用途。

圖上的邊可以擁有權重,可做其他用途。

有向圖比較特別。如果有向圖的邊有負的權重,有時候會被視為是反向關聯,可以把權重調整成正的權重,然後顛倒邊的方向。這只是有時候可以這麼做,並不一定每一種情況都得這麼做。

替點和邊取名字、代號

點和邊上面可以取名字、代號,方便辨認。名字、代號可以寫在點和邊的旁邊,也可以寫在點的裡面、邊的上面,只要能表達清楚就好。

名字可以隨便取,簡單明瞭就好。書上通常是用英文字母及數字居多。

Graph資料結構

圖的資料結構

來談談如何利用程式語言來儲存一張圖吧!

最簡單的方式,莫過於用個陣列,來紀錄所有點與點之間的邊了。這種方式相當直觀,也非常節省空間,但是卻不適合用於計算(請各位讀過圖論其他主題後,再來思考看看)。所以這裡要介紹其他類型的方法。

儲存一張圖的方式有許多種,這裡要介紹其中兩種最常見的方法:adjacency matrix、adjacency lists。adjacency為「相鄰」之意,以邊相連接的兩個點,則稱這兩個點「相鄰」。

Adjacency Matrix

把一張圖上的點依序標示編號,然後建立一個方陣,來記錄連接資訊。方陣中的每一個元素都代表著某兩點的連接資訊。例如元素(0,1)記錄著第0點到第1點的連接資訊、元素(4, 2)記錄著第4點到第2點的連接資訊。如此一來,任一兩個點之間的資訊,都有對應的地方可用於記錄,纖悉無遺。

連接資訊可以是邊的數目,也可以是邊的權重,也可以儲存其他的資訊。

值得一提的是,adjacency matrix可以用來記錄邊的權重。但是它卻沒辦法紀錄點的權重,它也沒辦法同時記錄點和邊的權重。不過,要記錄點的權重,其實只要另外開一條陣列就行了,也不是什麼難事。

另外,當兩點之間的邊超過一條的時候,adjacency matrix沒辦法記錄權重,因為adjacency matrix的一個格子只能存入一個數字,沒辦法同時間存入多個數字。我們可以修改adjacency matrix的構造以存入更多數字,只是這不在討論範圍之內,各位可自行研究。

程式碼可以寫成這樣:

或者是這樣:

Adjacency Lists

把一張圖上的點依序標示編號,然後針對每一個點,串連、表列其相鄰的點。例如第4列之中所列的數字,即是與第4點相鄰的點。

程式碼可以寫成這樣:

或者是這樣:

如果當邊數不多時,有人會這樣寫:

如果還要記錄邊的權重的話,就變成這樣:

或者是這樣:

但是如果還要記錄點的權重,那就另外再開一條陣列吧。

總結

這份文件簡單的介紹了什麼是圖,以及兩種風格迥異的圖的資料結構。

「圖(graph)」的學問,稱做「圖論(graph theory)」。圖論在資訊科學中佔有重要的一環,應用範圍也很廣。之後本站還會介紹圖論當中幾個較特別的主題,請各位拭目以待。