Graph

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

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

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

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

Isomorphism / Isomorphic

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

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

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

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

Directed Graph（Digraph）

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

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

替點和邊加上權重

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

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

替點和邊取名字、代號

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

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

Edge List

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

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

struct Edge { int a, b; // 一條邊的起點與終點 }; Edge edge[4]; // 四條邊 void edge_list() { int e = 0; // 邊數 int a, b; // 一條邊的端點、另一個端點 while (cin >> a >> b) { edge[e].a = a; edge[e].b = b; e++; } }

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

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

Adjacency Matrix

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

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

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

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

int graph[5][5]; void adjacency_matrix() { for (int i=0; i<5; ++i) for (int j=0; j<5; ++j) graph[i][j] = 0; int a, b, w; // 一條邊的端點、另一個端點、邊的權重 while (cin >> a >> b >> w) graph[a][b] = w; }

Adjacency Lists

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

第一種，直覺的實作方式，採用陣列：

int list[5][100]; // 五個列表。每一個列表的相鄰邊數上限是100。 int size[5]; // 記錄每一個列表的元素有多少個 void adjacency_lists() { for (int i=0; i<5; ++i) size[i] = 0; int a, b; // 一條邊的端點、另一個端點 while (cin >> a >> b) list[a][size[a]++] = b; }

第二種，古板的實作方式，採用串列：

struct Element { int b; Element* next; }; Element* list[5]; // 五個列表 void add_edge(int a, int b) { Element* e = new Element(); e->b = b; e->next = list[a]; list[a] = e; } void adjacency_lists() { for (int i=0; i<5; ++i) list[i] = 0; int a, b; // 一條邊的起點、終點 while (cin >> a >> b) add_edge(a, b); }

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

vector<int> list[5]; void adjacency_lists() { for (int i=0; i<5; ++i) list[i].clear(); int a, b; // 一條邊的起點、終點 while (cin >> a >> b) list[a].push_back(b); }

如果還要記錄邊的權重，就變成這樣：

int list[5][100]; int weight[5][100]; // 再開一個陣列來記錄邊的權重 int size[5]; struct Element { int b, w; // 同時記錄邊的權重 Element* next; }; Element* list[5]; struct Element {int b, w;}; // 同時記錄邊的權重 vector<Element> list[5]; vector< pair<int,int> > list[5]; // 用pair做為b和w

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

Adjacency Lists特殊的實作方式

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

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

本質上還是Adjacency Lists，只不過是調整了實作方式。外觀上像是Edge List與Adjacency Lists兩者合體。

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

struct Element { int b, w; // 同時記錄邊的權重 int next; // 串列指標改成陣列索引值 }; int list[5]; // adjacency lists int e = 0; // 邊數 Element edge[100]; // edge list void add_edge(int a, int b, int w) { // 設定這條邊的起點、終點、權重 e->b = b; e->w = w; // 把邊插入到對應串列開頭 e->next = list[a]; list[a] = e; e++; } void adjacency_lists() { e = 0; for (int i=0; i<5; ++i) list[i] = -1; int a, b, w; // 一條邊的起點、終點、權重 while (cin >> a >> b >> w) add_edge(a, b, w); }

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

int list[5]; int next[100], from[100], to[100], weight[100]; int e = 0; // 邊數 void add_edge(int a, int b, int w) { // 設定這條邊的起點、終點、權重 // from[e] = a; // 事實上不需要 to[e] = b; weight[e] = w; // 把邊插入到對應串列開頭 next[e] = list[a]; list[a] = e; e++; } void adjacency_lists() { e = 0; for (int i=0; i<5; ++i) list[i] = -1; int a, b, w; // 一條邊的起點、終點、權重 while (cin >> a >> b >> w) add_edge(a, b, w); }

Graph Traversal

給你一張圖，要怎麼讀出它的資訊呢？

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

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

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

利用最簡單的資料結構queue和stack，就能製造不同的遍歷順序，得到兩種遍歷演算法：Breadth-first Search和Depth-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是邊數。

程式碼

bool adj[9][9]; // 一張圖，資料結構為adjacency matrix。 bool visit[9]; // 記錄圖上的點是否遍歷過，有遍歷過為true。 void BFS() { // 建立一個queue。 queue<int> q; // 全部的點都初始化為尚未遍歷 for (int i=0; i<9; i++) visit[i] = false; for (int k=0; k<9; k++) if (!visit[k]) { // 一、把起點塞入queue。 q.push(k); visit[k] = true; // 二、重複下述兩點，直到queue裡面沒有東西為止： while (!q.empty()) { // 甲、queue彈出一點。 int i = q.front(); q.pop(); // 乙、找出跟此點相鄰的點，並且尚未遍歷的點， // 依照編號順序通通塞入queue。 for (int j=0; j<9; j++) if (adj[i][j] && !visit[j]) { q.push(j); visit[j] = true; } } } } // 很差的寫法，點從queue彈出之後才設定遍歷過了。 bool adj[9][9]; bool visit[9]; void BFS() { queue<int> q; for (int i=0; i<9; i++) visit[i] = false; for (int k=0; k<9; k++) if (!visit[k]) { q.push(k); while (!q.empty()) { int i = q.front(); q.pop(); if (!visit[i]) { visit[i] = true; for (int j=0; j<9; j++) if (adj[i][j] && !visit[j]) q.push(j); } } } }

Depth-first Search（DFS）

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

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

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

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

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

遞迴版本程式碼

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

bool adj[9][9]; // 一張圖，資料結構為adjacency matrix。 bool visit[9]; // 記錄圖上的點是否遍歷過，有遍歷過為true。 void DFS(int i) { for (int j=0; j<9; j++) if (adj[i][j] && !visit[j]) { visit[j] = true; // 標記為已遍歷 DFS(j); } } void traversal() { // 全部的點都初始化為尚未遍歷 for (int i=0; i<9; i++) visit[i] = false; for (int i=0; i<9; i++) if (!visit[i]) { visit[i] = true; DFS(i); } } bool adj[9][9]; bool visit[9]; void DFS(int i) { visit[i] = true; for (int j=0; j<9; j++) if (adj[i][j] && !visit[j]) DFS(j); } void traversal() { for (int i=0; i<9; i++) visit[i] = false; for (int i=0; i<9; i++) if (!visit[i]) DFS(i); } bool adj[9][9]; bool visit[9]; void DFS(int i) { if (visit[i]) return; visit[i] = true; for (int j=0; j<9; j++) if (adj[i][j]) DFS(j); } void traversal() { for (int i=0; i<9; i++) visit[i] = false; for (int i=0; i<9; i++) DFS(i); }

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

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

製圖時，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]

先看個圖片

圖片中省略了點的編號。

degree

一個點的「度」：一個點的邊數量。

有向圖，細分成入邊數量in-degree、出邊數量out-degree。

neighbor

一個點的「鄰居」：一個點連往的點。可能有許多個、零個。

無向圖，鄰居數量是邊數量。有向圖，鄰居數量是出邊數量。

順便補充幾個常見形容詞。

adjacent：相鄰、鄰接。只走一步，可以抵達。
connected：相連、連通。不限步數，可以抵達。

distance

兩個點的「距離」：從起點走到終點的邊數量，數量必須最低。

如果兩點之間不連通，距離是無限大。約定成俗。

指定起點，實施Breadth-first Search，就可以算出起點走到圖上各點的距離。利用這種方式，可以算出兩點之間的距離。大家可以試試看！

額外補充一下。當數量必須最低，改成了數量必須最高，則無法透過遍歷演算法求得答案，只能透過Backtracking窮舉所有路線，一一判斷答案。數量必須最高，已被證明是NP-complete問題，目前沒有（以後大概也不會有）快速的演算法。

順便補充幾個罕見名詞。

eccentricity：偏心距。從一個點出發的最長距離。
diameter：直徑。一張圖（的每個起點之中）最長的偏心距。一張圖最長的距離。
radius：半徑。一張圖（的每個起點之中）最短的偏心距。

Intersection Graph

圖用來表達兩兩之間的關係。例如一群人，我們可以建立「朋友關係」的圖，兩個人是朋友就連一條邊，兩個人不是朋友就沒有邊。只要是兩兩之間的關係，就得以轉化成圖，運用圖論知識來分析問題。

其中有個值得一提的關係是「交集關係」，是聯集交集的那個交集。兩個東西有交集就連一條邊（交集不是空集合）、沒交集就沒有邊（交集是空集合），最後得到的圖叫做「交集圖」。

例如一堆線段，把互相接觸的線段，表示成圖：

例如一堆集合，把有交集的集合，表示成圖：

比較特別的交集圖，數學家會特地取名。例如一堆硬幣，平鋪在桌上，把互相接觸的硬幣，表示成圖，稱作Coin Graph。數學家發現硬幣圖和平面圖兩者完全等價，每一種平面圖都可以利用硬幣接觸兜出來。

例如行程表，把撞期的行程，表示成圖，稱作Interval Graph，有著很特別的數學性質。

例如一張圖論的圖，把共用端點的邊，表示成圖，稱作Line Graph。

為什麼數學家特別重視交集圖呢？我也不知道。

很多人把交集圖看做是一個物品。但是交集圖其實是一種變換的概念，可以看做是一個函數。

Dependency Graph【尚無正式名稱】

除了「交集關係」之外，數學家也很重視「依賴關係」。把各個東西的仰賴對象表示成圖，最後得到的圖叫做「依賴圖」。

例如一堆不等式，把變數大小關係，表示成圖：

比較特別的依賴圖，數學家會特地取名。例如專案管理領域，把工作先後次序，表示成圖，稱作「Activity Network」。

例如2-SAT問題，把各個clause裡面的兩個變數的取捨關係，表示成圖，稱作「Implication Graph」。

交集圖是無向圖、依賴圖是有向圖，剛好一對。

UVa 10926

Subgraph / Supergraph

一張圖，刪除一些點、一些邊，得到的圖稱作「子圖」。

原圖（沒有刪除）、空圖（完全刪除），也算是「子圖」。

一張圖，增加一些點、一些邊，得到的圖稱作「父圖」。

原圖（沒有增加）也算是「父圖」。

subgraph和supergraph是相對的。如果A是B的子圖，那麼B就是A的父圖。我們習慣只講子圖，講一個就等於兩個都講了。

Induced Subgraph / Induced Supergraph

一張圖，保留一些點、以及這些點之間的所有邊，得到的圖稱作「導出子圖」。

一張圖，增加一些點、一些邊，但是不在原本的點之間增加邊，使得原本的圖是導出子圖，得到的圖稱作「導出父圖」。

induced subgraph和induced supergraph是相對的。如果A是B的導出子圖，那麼B就是A的導出父圖。我們習慣只講導出子圖，講一個就等於兩個都講了。

Minor / Subdivision

一張圖，收縮一些邊、合併一些點，得到的圖稱作minor。

收縮的邊，有人視情況刪除，也有人視情況不刪除、而變成連向自己的邊。

一張圖，在邊上植入點，得到的圖稱作subdivision。

minor和subdivision是相對的。一般只討論minor。

ICPC 4023

Oriented Graph / Underlying Graph

一張無向圖，無向邊改成有向邊，稱做「定向圖」。

一張有向圖，有向邊改成無向邊，稱作「底圖」。

定向圖和底圖是相對的。一般只討論定向圖。

Complement Graph（Complement）

一張圖，兩點之間沒邊變有邊、有邊變沒邊，稱作「補圖」。

原圖暨補圖的所有邊，合起來是完全圖。

朋友變仇人、有關變無關，整個相反顛倒，就是補圖的用處。

Reverse Graph（Transpose）

一張有向圖，邊的方向顛倒，稱作「反向圖」。

主動變被動、前進變後退，整個相反顛倒，就是反向圖的用處。

Line Graph

一張圖當中，觀察邊與邊關係，相鄰的邊表示成一張圖，稱作「線圖」。

UVa 10988 11175

Dual Graph

一張平面圖當中，觀察面與面關係，共邊的面表示成一張圖，稱作「對偶圖」。詳情請參考「Planar Graph」。

Hypergraph

「圖」是談兩個東西之間的關係，「超圖」則是談多個東西之間的關係，例如三個東西之間的關係。

超圖的資料結構，不適合採用Adjacency Matrix，因為矩陣必須變成多個維度，浪費記憶體空間。比較好的方式是採用Incidence Matrix。

一般的圖就很夠用了，通常不會用到超圖。