graph

graph

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

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

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

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

isomorphism / isomorphic

isomorphism中文譯作「同構」,isomorphic中文譯作「同構的」。如果兩張圖的連接方式一模一樣時,則稱作「同構」。

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

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

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

directed graph(digraph)

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

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

替點和邊加上權重

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

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

替點和邊取名字、代號

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

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

graph資料結構: edge list

edge list

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

「邊表」。一條陣列,或者串列,記錄所有點與點之間的邊。

這種資料結構相當簡單直觀,也非常節省空間,卻不適合用於計算──無法迅速找到一個點碰觸的所有邊。

因此大家又發明了其他的方式,這裡介紹其中兩種最常見的方式:adjacency matrix、adjacency lists。adjacency為「相鄰」之意,以邊相連接的兩個點,則稱這兩個點「相鄰」。

graph資料結構: adjacency matrix

adjacency matrix

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

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

adjacency matrix可以記錄邊的權重,但是無法記錄點的權重,也無法同時記錄點和邊的權重。不過呢,想要記錄點的權重,只需另外建立一條陣列,不是什麼難事。

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

graph資料結構: adjacency lists

adjacency lists

「相鄰列表」。把一張圖上的點依序標示編號。每一個點,後方列出所有相鄰的點。例如第4列是第4點所有相鄰的點。另外,相鄰的點也可以想成是相鄰的邊。

第一種,直覺的實作方式,採用陣列:

第二種,古板的實作方式,採用串列:

第三種,輕鬆的實作方式,利用程式語言內建的vector或list:

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

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

adjacency lists特殊的實作方式

中文網路稱作「链式前向星」,命名品味令人嘆為觀止。

整併所有列表,置於一條陣列,或者一條串列。順序可以相間。

本質上還是adjacency lists,只不過是調整了實作方式。外觀上像是edge list與adjacency lists兩者合體。

第四種,特殊的實作方式,記憶體取自陣列,不必new。

第五種,懶惰的實作方式,資料項目拆開成許多陣列。

graph traversal

graph traversal

給你一張圖,要怎麼讀出它的資訊呢?

用人眼來觀察一張圖,很快的就能看出點和線,一點一點釐清關係。要是一張圖能夠畫得漂亮一點,上個鮮明的顏色,那就更好了。

電腦則不然。要以電腦來讀取一張圖的資訊(這資訊想必會以圖的資料結構來妥善儲存),唯一的方法就是透過程式語言,以及良好的演算法囉!

Traversal中文稱作「遍歷」。圖的遍歷,也就是指通盤地讀取圖的資訊:決定好從哪裡開始讀,依照什麼順序讀,要讀到哪裡為止。詳細地設計好流程,始能通盤地讀取圖的資訊;如果設計得漂亮,在解決圖的問題時,還可以一邊讀取圖的資訊,一邊順手解決問題呢!

利用最簡單的資料結構queue和stack,就能製造不同的遍歷順序,得到兩種遍歷演算法:breadth-first search和depth-first search。這兩個演算法充分了利用程式語言的特性,簡約而美麗,成為資訊領域不可不知的演算法。

graph traversal: breadth-first search

breadth-first search(BFS)

(依照編號順序)不斷找出尚未遍歷的點當作起點,進行下述行為:
 一、把起點塞入queue。
 二、重複下述兩步驟,直到queue裡面沒有東西為止:
  甲、queue彈出一點。
  乙、找出跟此點相鄰的點,並且尚未遍歷的點,
    通通(依照編號順序)塞入queue。

教科書都有一步一步的示意圖,這裡不再重畫,只做額外補充。

運用BFS遍歷整張圖,最後得到許多棵樹。單一的樹稱作BFS tree,所有的樹稱作BFS forest。

不同的起點,形成不同的BFS forest。我們習慣按照編號順序選擇下一個要拜訪的點,得到唯一一種BFS forest。

遍歷順序示意圖:每個點進入與離開queue的時刻

每個點進入queue的時刻以左上深色數字表示,每個點離開queue的時刻以右下淺色數字表示。每個點都會進入queue一次、離開queue一次,不會再有第二次。

遍歷順序示意圖:每個點離開queue的時刻

只觀察離開queue的時刻,可以發現BFS優先走遍距離起點最近之處,優先讓BFS tree變得寬廣,因而得名breadth-first search。這個遍歷順序能夠解決許多圖論問題!

時間複雜度

圖的資料結構為adjacency matrix是O(V²);圖的資料結構為adjacency lists是O(V+E)。V是點數,E是邊數。

程式碼

graph traversal: depth-first search

depth-first search(DFS)

DFS與BFS大同小異,只是把queue換成了stack而已。

遍歷順序示意圖:每個點進入與離開stack的時刻

每個點進入stack的時刻以左上深色數字表示,每個點離開stack的時刻以右下淺色數字表示。每個點都會進入stack一次、離開stack一次,不會再有第二次。

遍歷順序示意圖:每個點離開stack的時刻

只觀察離開stack的時刻,可以發現DFS優先走遍距離起點最遠之處,優先讓DFS tree變得深遠,因而得名depth-first search。這個遍歷順序能夠解決許多圖論問題!

遞迴版本程式碼

DFS的程式碼也可以寫成遞迴形式。程式語言中的遞迴,其實就是利用stack來實作的。

遍歷順序示意圖:每個點進入遞迴與離開遞迴的時刻

進入遞迴的時刻以左上深色數字表示,離開遞迴的時刻以右下淺色數字表示。這個順序用於解決一些特別的圖論問題。

製圖時,DFS tree高度至少是三、分枝數目至少是三,比較容易觀察出遍歷順序。建議讀者也自己畫個圖、寫段程式研究一下。

邊的分類

藉由一叢DFS forest,一張有向圖的邊可以分成四類:

tree edge:樹上的邊。
back edge:連向祖先的邊。(形成環)
forward edge:連向子孫的邊。
cross edge:枝葉之間的邊、樹之間的邊。(可能形成環)

藉由一叢DFS forest,一張無向圖的邊可以分成兩類:

tree edge:樹上的邊。
back edge:連向祖先的邊。(形成環)

這些邊的分類,可以協助我們解決複雜的圖論問題。

d[x] : 節點 x 進入遞迴的時刻
f[x] : 節點 x 離開遞迴的時刻
(i,j) is a tree edge or a forward edge : d[i] < d[j] < f[j] < f[i]
(i,j) is a back edge : d[j] < d[i] < f[i] < f[j]
(i,j) is a cross edge : d[j] < f[j] < d[i] < f[i]