# Chap. 06 - Graph
> 課程內容 : 中興大學應用數學系 顏增昌教授 (111 學年度第 1 學期)
> 參考書目 : Fundamentals of Data Structures in C (2nd), Ellis H., Sartaj S., Susan A.-F.
>
>其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)
## Content
* [Sec. 6.1 ADT of graph](#Sec-61-ADT-of-graph)
* [1. Introduction](#1-Introduction)
* [1.1 Vertic and edge](#11-Vertic-and-edge)
* [1.2 Graph](#12-Graph)
* [1.3 Restriction](#13-Restriction)
* [1.4 Adjacent](#14-Adjacent)
* [1.5 Subgraph](#15-Subgraph)
* [1.6 Path](#16-Path)
* [1.7 Connected](#17-Connected)
* [1.8 Degree](#18-Degree)
* [2. Representation](#2-Representation)
* [2.1 Adjacency mxtrix](#21-Adjacency-mxtrix)
* [2.2 Adjacency list](#22-Adjacency-list)
* [Sec. 6.2 Elementary graph operation](#Sec-62-Elementary-graph-operation)
* [1. Depth first search](#1-Depth-first-search)
* [2. Breadth first search](#2-Breadth-first-search)
* [2.1 Implement of search](#21-Implement-of-search)
* [3. Connected components](#3-Connected-components)
* [3.1 Implement of connected component](#31-Implement-of-connected-component)
* [4. Spanning tree](#4-Spanning-tree)
* [5. Biconnected components](#5-Biconnected-components)
* [5.1 Implement of computing dfn and low](#51-Implement-of-computing-dfn-and-low)
* [5.2 Find biconnected component](#52-Find-biconnected-component)
## Sec. 6.1 ADT of graph
### 1. Introduction
#### 1.1 Vertic and edge
一個圖(graph)包含了兩個集合 $V$ 與 $E$，分別表示頂點(vertex)與邊(edge)的集合。以 $V(G)$ 和 $E(G)$ 表示圖 $G = (V, E)$ 的頂點集合與邊集合。
* $V$ 是一個有限且非空的頂點集合
* $E$ 是頂點對所形成的集合，每組成對的頂點對(vertice pair)稱為邊
#### 1.2 Graph
無向圖(undirected graph)表示邊的頂點對的順序沒有限制(下圖 $G_1$ 和 $G_2$)。假設 $u, v \in V(G)$，則 $(u, v)$ 與 $(v, u)$ 是同一條邊。
有向圖(directed graph)中邊的頂點對的順序是不同的(下圖 $G_3$)。假設 $u, v \in V(G)$，則邊 $(u, v)$ 表示一個由 $u$ 指向 $v$ 的邊，其中 $u$ 是尾端(tail)，$v$ 是頭端(head)
對於一個具有 n 個頂點的圖，若圖的邊數 = 最大邊數，則稱為完全圖(complete graph)
* 對 n 個頂點的無向圖，最大邊數 $= \cfrac{n(n-1)}{2}$
* 對 n 個頂點的有向圖，最大邊數 $= n(n-1)$
上圖 $G_1$ 為一個完全圖，且頂點與邊的集合分別為
$$
\begin{align}
&V(G_1) = \{0, 1, 2, 3\}\\
&E(G_1) = \{(0,1),(0,2),(0,3),(1,2),(1,3)(2,3)\}
\end{align}
$$
上圖 $G_3$ 為一個不完全圖(imcomplete graph)，且頂點與邊的集合分別為
$$
\begin{align}
&V(G_3) = \{0, 1, 2\}\\
&E(G_3) = \{(0, 1), (1, 0), (1, 2)\}
\end{align}
$$
#### 1.3 Restriction
* 自我邊(self edge)的限制(下圖左)
* 從相同頂點出發與結束的邊稱為自我邊(self edge)或自我迴圈(self loop)
* 圖不可包含自我邊，包含自我邊的圖稱為自我邊的圖(graph with self edge)
* 多邊圖的限制(下圖右)
* 相同的邊重複出現，稱為多邊圖(multigraph)
* 圖不可為多邊圖
:::info
這邊所指限制是只討論不具有自我邊與多邊圖性質的圖
:::
#### 1.4 Adjacent
(1) 在無向圖 $G$ 中，若 $(v_0, v_1) \in E(G)$ 是一條無向邊，則稱
* 頂點 $v_0$ 與 $v_1$ 是相鄰的(adjacent)
* 邊 $(v_0, v_1)$ 依附(incident)在頂點 $v_0$ 和 $v_1$ 上
(2) 在有向圖 $G'$ 中，若 $(v_0, v_1) \in E(G')$ 是一條有向邊，則稱
* 頂點 $v_0$ 相鄰到(adjacent to)頂點 $v_1$
* 頂點 $v_1$ 由頂點 $v_0$ 相鄰過來(adjacent from)
#### 1.5 Subgraph
滿足以下兩點，則稱 $G'$ 是 $G$ 的子圖
1. $V(G') \subseteq V(G)$
2. $E(G') \subseteq E(G)$
#### 1.6 Path
* Path(路徑)：由頂點 $u$ 到頂點 $v$ 的路徑是由多個頂點 $u,\ i_1,\ i_2,\ ...,\ i_k,\ v$ 所組成的序列，使得 $(u,i_1), (i_1, i_2), ..., (i_k, v) \in E(G)$。
* 路徑長(length of path) 指的是路徑上的邊數。
* Simple path(簡單路徑)：路徑上除了頂點與終點外，其餘頂點都不相同的圖形稱為簡單路徑
* Cycle(循環圖)：起點與終點相圖的簡單路徑
#### 1.7 Connected
(1) Connected(連接)
* 在無向圖 $G$ 中，若存在一條從頂點 $u$ 到頂點 $v$ 的路徑(path)，則稱頂點 $u$ 和頂點 $v$ 是連接的(connected)
* 對於所有頂點 $u, v \in V(G)$，若 $u$ 與 $v$ 是連通的，則無向圖 $G$ 是可連接的(connected graph)
如下圖，圖左是連通圖(connected graph)，圖右為非連通圖(disconnected graph)
(2) Connected component
* Maximal connected subgraph
* 無向圖 $G$ 裡不存在一個連通子圖包含 $H$ 且不等於 $H$，則 $H$ 稱為最大連通子圖(maximal connected subgraph)
* Connected component
* 無向圖 G 的連通元件(connected component)是一個最大可連接子圖
(3) Strongly connected
* 在有向圖 $G$ 中，若存在一條從頂點 $u$ 到 $v$ 的路徑和另一條從頂點 $v$ 到 $u$ 的路徑，則稱頂點 $u$ 和 $v$ 是強連接(strongly connected)
* 對於所有頂點 $u, v \in V(G)$，若 $u$ 與 $v$ 是 strongly connectd，則有向圖 $G$ 是強連通的(strongly connected)
(4) Strongly connected component
* Maximal strongly connected subgraph
* 有向圖 $G$ 裡不存在一個強連通子圖 $H$ 且不等於 $H$，則 $H$ 稱為最大強連通子圖(maximal strongly connected subgraph)
* Strongly connected component
* 有向圖 $G$ 的強連通元件(strongly connected component)是一個最大強連通子圖
#### 1.8 Degree
頂點的分支度(degree)指的是接在頂點上的邊的數量。在有向圖中，
* 頂點 $v$ 的入分支度(in-degree)指的是以頂點 v 為頭(head)的邊數(進入 $v$)
* 頂點 $u$ 的出分支度(out-degree)指的是以頂點 v 為尾(tail)的邊數(從 $u$ 出發)
### 2. Representation
圖(graph)有 3 種常見的表示法: (1) 相鄰矩陣(adjacency matrix) (2) 相鄰串列(adjacency list) 與 (3) 相鄰多重串列(adjacency multilists)
#### 2.1 Adjacency mxtrix
設 $G(V, E)$ 為一個有 $n$ 個頂點的圖，則 $G$ 的相鄰矩陣為一個 $n \times n$ 的二維矩陣。若邊 $(v_i, v_j) \in E(G)$，則 $a[i][j] = 1$，反之則 $a[i][j] = 0$。
> 無向圖的相鄰矩陣必為對稱(symmetric)矩陣
:::info
相鄰矩陣的表示法缺點是浪費空間，因為類似稀疏矩陣
:::
#### 2.2 Adjacency list
將相鄰矩陣的 $n$ 列表示成 $n$ 個鏈結(link)，圖 $G$ 中的每個頂點都有一個鏈，鏈 $i$ 中的節點表示從頂點 $i$ 出發且與 $i$ 相鄰的頂點(adjacent from vertex $i$)。
若使用一個陣列 `adjList` 來表示所有頂點的相鄰串列，則能夠在 $O(1)$ 的時間內存取任一頂點 $i$ 的相鄰串列。
以 adjacent list 建立或表示圖的時候，陣列 `adjList` 中的每個位置都是一個 linked list。
而建立圖的過程其實就是把頂點兩兩一組用邊(edge)聯繫起來，也就是在每個 linked list 建立與插入頂點。如下圖為在圖 $G$ 中新增一個頂點 3。
<img src="https://hackmd.io/_uploads/SJAOqOhwJl.jpg" width=300>
> The following code is saved in `basicOperation.c`.
```c=
nodePointer createNode(int vertex){
nodePointer node;
MALLOC(node, sizeof(struct node));
node->vertexIdx = vertex;
node->link = NULL;
return node;
}
void addEdge(nodePointer adjList[], int src, int dst){
// from src to dst
nodePointer dstNode = createNode(dst);
dstNode->link = adjList[src];
adjList[src] = dstNode;
// from dst to src, bidirect graph don't need this segment
nodePointer srcNode = createNode(src);
srcNode->link = adjList[dst];
adjList[dst] = srcNode;
}
void printAdjList(nodePointer adjList[], int graphSize){
/* print adjacent list of graph */
for (int i = 0; i < graphSize; i++){
printf("adjList[%d]:", i);
nodePointer temp = adjList[i];
while (temp){
printf(" %d", temp->vertexIdx);
temp = temp->link;
}
puts("");
}
}
void resetVisited(int visited[]){
/* reset visited array with some graph */
for (int i = 0; i < MAXSIZE; i++){
visited[i] = FALSE;
}
}
void freeList(nodePointer adjList[], int graphSize){
for (int i = 0; i < graphSize; i++){
nodePointer current = adjList[i];
while (current){
nodePointer temp = current;
current = current->link;
free(temp);
}
adjList[i] = NULL;
}
}
```
`addEdge()` 中的第一段是指從頂點 src 出發並連結到頂點 dst。如果是無向圖則需要反向(dst to src)再建立一條邊。
另外，因為加入邊的順序不同，所以同一個圖 adjacent list 的表示法不唯一。以下圖為例，使用上述程式碼建立邊後的表示法如下
```c=
/** example undirect graph with 8 vertex
* adjList[0]: 1 -> 2 -> NULL
* adjList[1]: 0 -> 3 -> 4 -> NULL
* adjList[2]: 0 -> 5 -> 6 -> NULL
* adjList[3]: 1 -> 7 -> NULL
* adjList[4]: 1 -> 7 -> NULL
* adjList[5]: 2 -> 7 -> NULL
* adjList[6]: 2 -> 7 -> NULL
* adjList[7]: 3 -> 4 -> 5 -> 6 -> NULL
*/
int main(void){
int graphSize = 8;
nodePointer adjList[graphSize];
for (int i = 0; i < graphSize; i++){
adjList[i] = NULL;
}
// the example graph has 10 edges
addEdge(adjList, 0, 1);
addEdge(adjList, 0, 2);
addEdge(adjList, 1, 3);
addEdge(adjList, 1, 4);
addEdge(adjList, 2, 5);
addEdge(adjList, 2, 6);
addEdge(adjList, 3, 7);
addEdge(adjList, 4, 7);
addEdge(adjList, 5, 7);
addEdge(adjList, 6, 7);
printAdjList(adjList, graphSize);
freeList(adjList, graphSize);
}
/** output
* adjList[0]: 2 1
* adjList[1]: 4 3 0
* adjList[2]: 6 5 0
* adjList[3]: 7 1
* adjList[4]: 7 1
* adjList[5]: 7 2
* adjList[6]: 7 2
* adjList[7]: 6 5 4 3
*/
```
##### Inverse adjacency list (反相鄰串列)
相鄰串列主要是記錄每個頂點的 out-deree，因此串列 $i$ 的節點表示每個從頂點 $i$ 出發的邊的終端節點。
反相鄰串列(inverse adjacency list)則是紀錄每個頂點的 in-degree，因此串列 $i$ 的節點表示每個以頂點 $i$ 為終點的邊的起始節點。
## Sec. 6.2 Elementary graph operation
### 1. Depth first search
圖的走訪有兩種: (1) 深度優先搜索(depth-first-search, dfs)與 (2) 廣度優先搜索(breadth-first-search, bfs)。深度優先搜索類似樹的前序走訪(preorder traversal)，可以使用遞迴(recursion)或 stack 實作。
* 決定一個頂點拜訪
* 從該頂點的相鄰頂點中選一個
* 沒拜訪過，拜訪此頂點並重回第二步
* 已拜訪過，再選擇下一個相鄰頂點
因為圖的連接可能會包含循環(cycle)，為了避免走到重複的點所以需要用一個陣列儲存已被走訪過的頂點。如下圖所示，走訪的順序為：0, 1, 3, 7, 4, 5, 2, 6
(實際走訪順序可能因起點不同或是相鄰鏈結串列中頂點位置不同而有差異)
#### Recursion ver.
> The following code is saved in `search.c`.
```c=
void dfsUsingRecursion(nodePointer adjList[], int visited[], int startVertex){
visited[startVertex] = TRUE;
printf(" %d", startVertex);
nodePointer current = adjList[startVertex];
while (current){
if (!visited[current->vertexIdx]){
dfsUsingRecursion(adjList, visited, current->vertexIdx);
}
current = current->link;
}
}
```
#### Stack ver.
> The following code is saved in `search.c`.
```c=
void dfsUsingStack(nodePointer adjList[], int visited[], int startVertex){
int stack[MAXSIZE];
int top = -1;
stack[++top] = startVertex;
while (top != -1){
int vertex = stack[top--];
if (!visited[vertex]){
printf(" %d", vertex);
visited[vertex] = TRUE;
}
nodePointer temp = adjList[vertex];
while (temp != NULL){
if (!visited[temp->vertexIdx]){
stack[++top] = temp->vertexIdx;
}
temp = temp->link;
}
}
}
```
### 2. Breadth first search
廣度優先的搜索類似樹的階層走訪(level traversal)，使用一個 queue 實作
* 決定一個頂點做為起頂點
* 拜訪起始頂點 $v$
* 拜訪所有與 $v$ 相鄰的點(相同相鄰串列中)
* 都拜訪過，則找 $v$ 的相鄰頂點中的第一個拜訪過的
* 重回第三步驟
每走訪一個頂點就加入到 queue 之中，當拜訪完該點的相鄰串列的所有點後，從 queue 取出一個頂點並檢查它的相鄰串列：
* 沒拜訪過：拜訪並加入到 queue
* 拜訪過：略過
以下圖為例，走訪的順序為: 0, 1, 2, 3, 4, 5, 6, 7
> The following code is saved in `search.c`.
```c=
void bfs(nodePointer adjList[], int visited[], int startVertex){
int queue[MAXSIZE];
int front = 0;
int rear = 0;
printf(" %d", startVertex);
visited[startVertex] = TRUE;
queue[rear++] = startVertex;
while (front < rear){
int vertex = queue[front++];
for (nodePointer current = adjList[vertex]; current; current = current->link){
if (!visited[current->vertexIdx]){
printf(" %d", current->vertexIdx);
visited[current->vertexIdx] = TRUE;
queue[rear++] = current->vertexIdx;
}
}
}
}
```
#### 2.1 Implement of search
> The following is saved in `search-implement`.
```c=
#include "GraphADT.h"
#include <stdio.h>
int main(void){
// prepare graph with 8 vertex
int graphSize = 8;
nodePointer adjList[graphSize];
for (int i = 0; i < graphSize; i++){
adjList[i] = NULL;
}
int visited[MAXSIZE];
resetVisited(visited);
// the example graph has 10 edges
addEdge(adjList, 0, 1);
addEdge(adjList, 0, 2);
addEdge(adjList, 1, 3);
addEdge(adjList, 1, 4);
addEdge(adjList, 2, 5);
addEdge(adjList, 2, 6);
addEdge(adjList, 3, 7);
addEdge(adjList, 4, 7);
addEdge(adjList, 5, 7);
addEdge(adjList, 6, 7);
printAdjList(adjList, graphSize);
printf("dfsUsingRecursion(0):");
dfsUsingRecursion(adjList, visited, 0);
puts("");
resetVisited(visited);
printf("dfsUsingStack(0):");
dfsUsingStack(adjList, visited, 0);
puts("");
resetVisited(visited);
printf("bfs(0):");
bfs(adjList, visited, 0);
puts("");
resetVisited(visited);
freeList(adjList, graphSize);
}
/* output
adjList[0]: 2 1
adjList[1]: 4 3 0
adjList[2]: 6 5 0
adjList[3]: 7 1
adjList[4]: 7 1
adjList[5]: 7 2
adjList[6]: 7 2
adjList[7]: 6 5 4 3
dfsUsingRecursion(0): 0 2 6 7 5 4 1 3
dfsUsingStack(0): 0 1 3 7 4 5 2 6
bfs(0): 0 2 1 6 5 4 3 7
*/
```
(實際走訪結果會因相鄰鏈結串列的表示法的順序不同而相異)
### 3. Connected components
對於一個無向圖 $G$，可以藉由呼叫 `dfs(0)` 或 `bfs(0)` 的結果來判斷一個 $G$ 是不是 connected
* 若完全走訪，沒有剩餘頂點：connected graph
* 有剩餘頂點：disconnected graph
如果是非連接圖(non-connected graph)的話，透過重複的呼叫 `dfs(i)` 或 `bfs(i)` 可以找出非連接圖的連通元件(connected components)，其中 `i` 是尚未拜訪的頂點。
> The following code is saved in `findConnected.c`.
```c=
void findConnected(nodePointer adjList[], int visited[], int graphSize){
puts("Connected component:");
for (int i = 0; i < graphSize; i++){
if (!visited[i]){
bfs(adjList, visited, i);
puts("");
}
}
}
```
#### 3.1 Implement of connected component
以下圖的為例
> The following code is saved in `findConnected-implement.c`.
```c=
int main(){
// create disconnected graph with 8 vertics and 10 edges
int graphSize = 8;
nodePointer adjList[graphSize];
for (int i = 0; i < graphSize; i++){
adjList[i] = NULL;
}
int visited[MAXSIZE];
resetVisited(visited);
addEdge(adjList, 0, 1);
addEdge(adjList, 1, 2);
addEdge(adjList, 1, 3);
addEdge(adjList, 4, 5);
addEdge(adjList, 4, 6);
addEdge(adjList, 6, 7);
printAdjList(adjList, graphSize);
findConnected(adjList, visited, graphSize);
resetVisited(visited);
freeList(adjList, graphSize);
return 0;
}
/* output
adjList[0]: 1
adjList[1]: 3 2 0
adjList[2]: 1
adjList[3]: 1
adjList[4]: 6 5
adjList[5]: 4
adjList[6]: 7 4
adjList[7]: 6
Connected component:
0 1 3 2
4 6 5 7
*/
```
### 4. Spanning tree
> A spaning tree is a subset of graph G such that all the vertices are connected using minimum possible number of edges.
換言之，任何一個只包含 $G$ 裡的邊以及 $G$ 裡的所有頂點的樹，稱為生成樹(spanning tree)。如下圖所示，一個圖 G 中會有多個生成樹。
Spanning tree 的性質如下：
* 非連接圖(disconnected graph)中不存在生成樹
* 對於一個有 N 個頂點的連接圖，其生成樹的邊的個數為 N - 1
生成樹可以使用 DFS 或 BFS 建立，使用 DFS/BFS 建立的生成樹稱為深度/廣度優先生成樹。因為雖然 DFS 或 BFS 在走訪圖時會經過所有的頂點，但不會經過所有的邊，因此整個搜索的過程其實隱含著把圖的邊分成兩個集合
* 走訪過的邊
* 沒有走訪過的邊
走訪過的邊與所有頂點組合在一起就是一個生成樹。又因為走訪的路徑不是唯一，所以生成樹的結構也不是唯一。
如下圖的結構與相鄰鏈結串列為例，以頂點 $0$ 為起點開始的 DFS 走訪順序為
| Vertex | Edge |
| :-: | :-: |
| 0 | |
| 1 | (0, 1) |
| 3 | (1, 3) |
| 7 | (3, 7) |
| 4 | (7, 4) |
| 5 | (7, 5) |
| 2 | (5, 2) |
| 6 | (2, 6) |
經過的邊分別為 $(0, 1),\ (1, 3),\ (3, 7),\ (7, 4),\ (7, 5),\ (5, 2),\ (2, 6)$，因此對應的 spanning tree 結構為
### 5. Biconnected components
(1) Articulation point(接合點)
無向圖 $G$ 中的頂點 $v$ 是一個接合點 $\Leftrightarrow$ 刪掉所有依附在 $v$ 的邊後，至少產生兩個可連接元件的圖。
如下圖所示，頂點 1, 3, 5, 7 是此圖的接合點
<img src="https://hackmd.io/_uploads/HkzH1aVDye.jpg" width=400>
(2) Biconnected graph(雙連通圖)
雙連接圖是一個沒有接合點的連接圖，如下圖所示
<img src="https://hackmd.io/_uploads/H1aICnEvyl.png" width=500>
在某些應用領域中不希望圖有連接點，以通訊網路為例，如果網路圖具有接合點，則可能在某個節點斷掉時會造成整個網路癱瘓。
(3) Biconnected components(雙連通元件)
連接圖 $G$ 的雙連通元件 $H$ 指的是 $G$ 的最大雙連接子圖，也就是找不到其他包含 $H$ 的雙連接圖。如下圖所示，包含了 6 個雙連通元件
:::info
(1) 深度優先號碼(dfn)
在進行 DFS 的時候，頂點被訪問的順序稱為深度優先號碼(depth first number, dfn)。以下中圖為例，以 $3$ 為起點進行 DFS 時頂點旁邊的數字代表他被訪為的順序
* $dfs(3) = 0$
* $dfs(0) = 4$
* $dfn(9) = 8$
將 spanning tree 以類似二元樹的方式呈現後可以發現若頂點 $u$ 在深度優先生成樹中是頂點 $v$ 的祖先，則 $dfn(u) < dfn(v)$
(2) 回邊(back edge)
如前所述，在進行 DFS 時會將圖的邊劃分為兩個集合，走訪過的邊會變成 spanning tree 的邊，其餘沒有走訪的邊則稱為回邊(back edge)，意即不在深度優先生成樹裡面的邊。如下圖右所示，虛線部分就是回邊。
:::
從圖的搜索路徑以及深度優先號碼，我們可以給定以下的定義：
$low(u)$ 表示從頂點 $u$ 開始，經過 $u$ 的後代與回邊後所組成的路徑，最後可以到達的最小 dfn。簡單來說就是能夠回到的最早祖先的 dfn。
$$
low(u) = \min\{ dfn(u),\ \min\{low(w)|w\ \text{is child of}\ u\},\ \min\{dfn(w)|(u,w)\ \text{is back edge}\}\}
$$
以上右圖為例，所有頂點的 dfn 值與 low 值如下：
| Vertex | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| $dfn$ | 4 | 3 | 2 | 0 | 1 | 5 | 6 | 7 | 9 | 8 |
| $low$ | 4 | 3 | 0 | 0 | 0 | 5 | 5 | 7 | 9 | 8 |
可以透過修改 `dfs()` 函式來計算各頂點的 dfn 與 low 值。
> The following code is saved in `findBiConnected.c`.
```c=
void init(int dfn[], int low[], int *count){
/* reset dfn, low, and count */
for (int i = 0; i < MAXSIZE; i++){
dfn[i] = -1;
low[i] = -1;
}
*count = 0;
}
void countDFNLOW(nodePointer *adjList, int *visited, int *dfn, int *low, int u, int parent, int *count){
visited[u] = TRUE;
printf(" %d", u); // show go through path
dfn[u] = low[u] = (*count)++;
nodePointer current = adjList[u];
while(current){
int vertex = current->vertexIdx; // next adjacent vertex
if (vertex == parent){ // if next vertex is parent
current = current->link; // go next adjacent vertex
continue;
}
// if next vertex didn't pass through
// go through next adjacent vertex and update low value of u
if (!visited[vertex]){
countDFNLOW(adjList, visited, dfn, low, vertex, u, count);
low[u] = MIN(low[u], low[vertex]);
}
// if next vertex have ever pass through
// check that the edge is back edge or not, then update low value of u
else{
low[u] = MIN(low[u], dfn[vertex]);
}
current = current->link;
}
}
```
綜上所述，對於一個連通的無向圖 $G$，可以利用 $G$ 的任何一個深度優先生成樹來找出它的雙連通元件(i.e., 找到接合點)：
* 若頂點 $u$ 是接合點 $\Leftrightarrow$ $u$ 是根節點且有兩個或兩個以上的子頂點
* 若頂點 $u$ 是接合點 $\Leftrightarrow$ $u$ 不是根節點且有一個子頂點 $w$ 使得 $low(w) \ge dfn(u)$
以上表與上右圖為例：
* 頂點 $1$ 是接合點，因為 $low(0) = 4 \ge dfn(1) = 3$
* 頂點 $3$ 是接合點，因為是根節點且有兩個子頂點
* 頂點 $5$ 是接合點，因為 $low(6) = 5 \ge dfn(5) = 5$
* 頂點 $7$ 是接合點，因為 $low(8) = 9 \ge dfn(7) = 7$
#### 5.1 Implement of computing dfn and low
> The following code is saved in `computeDFNLOW-implement.c`.
```c=
int main(void){
// prepare graph with 10 vertics
int graphSize = 10;
nodePointer adjList[graphSize];
for (int i = 0; i < graphSize; i++){
adjList[i] = NULL;
}
int visited[MAXSIZE];
resetVisited(visited);
addEdge(adjList, 0, 1);
addEdge(adjList, 1, 2);
addEdge(adjList, 1, 3);
addEdge(adjList, 2, 4);
addEdge(adjList, 3, 4);
addEdge(adjList, 3, 5);
addEdge(adjList, 5, 7);
addEdge(adjList, 5, 6);
addEdge(adjList, 6, 7);
addEdge(adjList, 7, 8);
addEdge(adjList, 7, 9);
printAdjList(adjList, graphSize);
int dfn[MAXSIZE];
int low[MAXSIZE];
int count;
init(dfn, low, &count);
printf("%s", "show traversal path: ");
countDFNLOW(adjList, visited, dfn, low, 3, -1, &count);
puts("");
printf("%s\n", "Vertex | 0 1 2 3 4 5 6 7 8 9");
printf("%s", "dfn |");
for (int i = 0; i < graphSize; i++){
printf(" %d", dfn[i]);
}
puts("");
printf("%s", "low |");
for (int i = 0; i < graphSize; i++){
printf(" %d", low[i]);
}
puts("");
freeList(adjList, graphSize);
return 0;
}
/* output
adjList[0]: 1
adjList[1]: 3 2 0
adjList[2]: 4 1
adjList[3]: 5 4 1
adjList[4]: 3 2
adjList[5]: 6 7 3
adjList[6]: 7 5
adjList[7]: 9 8 6 5
adjList[8]: 7
adjList[9]: 7
show traversal path: 3 5 6 7 9 8 4 2 1 0
Vertex | 0 1 2 3 4 5 6 7 8 9
dfn | 9 8 7 0 6 1 2 3 5 4
low | 9 0 0 0 0 1 1 1 5 4
*/
```
(一開始的起始頂點沒有父頂點，所以用 `-1`)
#### 5.2 Find biconnected component
在 `countDFNLOW()` 函式中加入其他條件，就可將圖的雙連通圖依照各雙連通元件的邊做切割。透過把第一次走訪的邊推入 stack 中，只要確認 $low(w) \ge dfn(u)$ ($w$ 是 $u$ 的子頂點)就可以找到接合點 $u$，再把與接合點相關的邊找出來。
> The following code is saved in `findBiConnected.c`.
```c=
void findBCC(nodePointer *adjList, int *visited, int *dfn ,int *low, int u, int parent, int *count, struct edge *stack, int *top){
visited[u] = TRUE;
dfn[u] = low[u] = (*count)++;
nodePointer current = adjList[u]; // next adjacent vertex
while (current){
int v = current->vertexIdx;
if (v == parent){
current = current->link;
continue;
}
// push to stack
// if dfn[v] < dfn[u] 的重要性在於 v 是子頂點，所以里碖上來說應該沒有被拜訪過，dfn[v] 應該比 dfn[u] 大
// 但當 dfn[v] < dfn[u] 時表示 v 已經在之前出現過了
// 現在這組 (u, v) 是一個回邊，是第二次出現，所以不用再推入 stack 中
if (dfn[v] < dfn[u]){
stack[++(*top)].u = u;
stack[*top].v = v;
}
if (!visited[v]){
findBCC(adjList, visited, dfn, low, v, u, count, stack, top);
low[u] = MIN(low[u], low[v]);
if (low[v] >= dfn[u]){ // u 是接合點
printf("articulation point: %d\n", u);
// pop from stack
int x, y;
do {
x = stack[*top].u;
y = stack[(*top)--].v;
printf(" (%d,%d)", x, y);
} while (!((x == u) && (y == v)));
puts("");
}
}
else if (dfn[v] < dfn[u]){
low[u] = MIN(low[u], dfn[v]);
}
current = current->link;
}
}
```
##### Implement
> The following code is saved in `findBiConnected-implement.c`.
```c=
int main(void){
// prepare graph with 10 vertics
int graphSize = 10;
nodePointer adjList[graphSize];
for (int i = 0; i < graphSize; i++){
adjList[i] = NULL;
}
int visited[MAXSIZE];
resetVisited(visited);
addEdge(adjList, 0, 1);
addEdge(adjList, 1, 2);
addEdge(adjList, 1, 3);
addEdge(adjList, 2, 4);
addEdge(adjList, 3, 4);
addEdge(adjList, 3, 5);
addEdge(adjList, 5, 7);
addEdge(adjList, 5, 6);
addEdge(adjList, 6, 7);
addEdge(adjList, 7, 8);
addEdge(adjList, 7, 9);
printAdjList(adjList, graphSize);
int dfn[MAXSIZE];
int low[MAXSIZE];
int count;
struct edge stack[MAXSIZE * (MAXSIZE / 2)];
int top = -1;
init(dfn, low, &count);
findBCC(adjList, visited, dfn, low, 3, -1, &count, stack, &top);
freeList(adjList, graphSize);
return 0;
}
/* output
adjList[0]: 1
adjList[1]: 3 2 0
adjList[2]: 4 1
adjList[3]: 5 4 1
adjList[4]: 3 2
adjList[5]: 6 7 3
adjList[6]: 7 5
adjList[7]: 9 8 6 5
adjList[8]: 7
adjList[9]: 7
articulation point: 7
(7,9)
articulation point: 7
(7,8)
articulation point: 5
(7,5) (6,7) (5,6)
articulation point: 3
(3,5)
articulation point: 1
(1,0)
articulation point: 3
(1,3) (2,1) (4,2) (3,4)
*/
```
Sign in with Wallet
Connect another wallet