# [資料結構] CH17. Advanced Graphs

* 繼續來看更多名詞吧...

## Articulation Point
* 關節點，若該點被移除，整個graph會被分為兩個部分。
* 下圖C、D就是**Articulation Point**。

graph articulation
{
    C [color="red"]
    D [color="red"]
    A -- B
    A -- C
    B -- D
    C -- D
    D -- E
    D -- F
    C -- H
    C -- J
    C -- I
    H -- J
    H -- I
    J -- I
}

## Bi-connected graph
* 雙向連接圖表示沒有任何**articulation point**的graph。

graph BiConnected
{
    A--B
    B--C
    D--C
    D--A
    {rank=same;A;B}
    {rank=same;C;D}
}

## Bridge
* 橋梁，若該邊被移除，整個graph會被分為兩個部分。
* 下圖中，e(A,B)和e(B,C)是bridge。

graph Bridge
{
    A--B--C--D--E--C
    {rank="same";D;E}
}

## Representation of Graphs
* 在電腦中儲存graph的方法通常有三種。

### Sequential Representation
* 若有`n`個node在這張圖中，我們就宣告一個`n*n`的二維矩陣來儲存它。
* 元素$a_{i,j}$表示從第$i$個點連到第$j$個點的邊有幾個。
* 下圖(d)為特例，儲存的是該邊的權重而不是邊的數量。
* 可以觀察到以下特性：
* 如果該graph沒有loop，對角線上的數字都會是`0`。
* 如果該graph是無向圖，矩陣會以對角線為軸映射。
* 如果該graph的邊不多，大多數的數字都會是`0`，因此矩陣會成為稀疏矩陣。
* 如果該graph沒有multiple edges，矩陣裡面就只會有`0`或`1`，此時的矩陣又稱做**bit matrix**或是**boolean matrix**。
* 這要畫圖我會畫到死，直接上圖片。
* 
---
* 將原矩陣寫作$A^1$，$a^1_{i,j}$也可以表示$v_i$到$v_j$長度為`1`的path數量。
* 將$A^1$做平方得到$A^2$，則$a^2_{i,j}$表示$v_i$到$v_j$長度為`2`的path數量。
* $A^3$、$A^4...A^n$，表示長度為`n`的path數量。
* 設`n`為該graph的node數量，$B^{n-1}=A^1+A^2+...+A^{n-1}$，$P_{i,j}=max(B^{n-1}_{i,j},1)$，則矩陣P表示從$v_i$到$v_j$是否存在path。

### Linked Representation
* 使用Linked-List的方法來記錄關係。
* 設立`n`個pointer，將第i個點有連到的邊都串在第i個pointer之後。
* 對於邊很少的時候是好選擇(用上面的矩陣會變成稀疏矩陣、浪費空間)。
* 

### Adjacency Multi-list
* 把每一個邊的資料存起來，再用指標串接關係。
* 資料通常有：
* 第一個點。
* 第二個點。
* 其他第一個點連到的邊。
* 其他第二個點連到的邊。
* 如果沒有其他連到的邊了，或是其他的邊已經被找過了，那就將其設為NULL。
* 

## Traversal Algorithms
* 當我們要遍歷一張graph所有的點時，我們有BFS和DFS兩種方式。

### Breadth-first Search
* 廣度優先搜索，使用**queue**儲存接下來要探索的點。
* 範例：從點A使用BFS找出A到I的最短路徑，優先度為英文字母越小的點先跑(ex:B先C後)。

digraph BFS
{
    A->B->E->C->G->I->F->H
    A->C
    A->D->G
    E->F->C
    D->C->B
    {rank="same";B;C;D;}
    {rank="same";E;F;G;}
}

* 先跑A，將BCD加入到queue裡面。
* ans: A
* queue: B, C, D
* 從queue裡面pop出下一個要跑的點，跑點B，將E加入到queue裡面。(ori為來源，我們要知道來源才能回推路徑。)
* ans: A, B
* ori: 0, A
* queue: C, D, E
* pop出點C，加入G，B跑過了所以不加。
* ans: A, B, C
* ori: 0, A, A
* queue: D, E ,G
* pop點D，沒有點可以加。
* ans: A, B, C, D
* ori: 0, A, A, A
* queue: E ,G
* pop點E，加入F。
* ans: A, B, C, D, E
* ori: 0, A, A, A, B
* queue: G, F
* pop點G，加入I。
* ans: A, B, C, D, E, G
* ori: 0, A, A, A, B, C
* queue: F, I
* 此時找到目標點I了，往回推是那些點導向它的。
* I是G找到的；G是C找到的；C是A找到的。
* 因此點A到I的最點path為A>C>G>I。

### Depth-first Search
* 深度優先搜索，使用**stack**儲存接下來要探索的點。
* 範例：使用DFS從點H，依順序輸出探索到的點。

digraph BFS
{
    A->B->E->C->G->I->F->H->E
    A->C
    A->D->G
    E->F->C
    D->C->B
    {rank="same";B;C;D;}
    {rank="same";E;F;G;}
}

* 先跑H，將E加到stack中。
* ans: H
* stack: E
* pop點E，加入CF。
* ans: H, E
* stack: C, F
* pop點F。
* ans: H, F
* stack: C
* pop點C，加入B。
* ans: H, E, F, C
* stack: B
* pop點B，stack沒東西了，結束。
* ans: H, E, F, C, B。

---

* BFS可以找最短路徑、DFS雖然也可以但比較麻煩。
* 這兩種演算法想要練習的話可以自行google經典題目**老鼠走迷宮**。

###### tags: `DS` `note`