---
tags: 資料結構
---
# 資料結構 第六章 圖形

## 一、圖形介紹
### (一)七橋問題

討論四個島嶼七座橋(將所有邊走過一次不重複)，將島嶼表示為頂點橋表示為邊，【參考離散數學】尤拉推導每個點degree(分支)需要皆為偶數，否則無法完成，或是(2點degree為奇數其餘為偶數)

### (二)圖形分別
#### 1、有向圖與無向圖
##### G~1~、G~2~為無向圖(0→1，1→0相同)，G~3~為有向圖(0→1，1→0不同)

#### 2、簡單圖與多重圖

##### G=<V,E>:圖形若G中任二點之間至多一邊相連，稱G為simple graph，否則稱G為mutigraph

### (三)子圖
#### 1、定義:G=<V,E>,則S為G的subgraph表示S = <V',E'>,其中V'屬於V,E'屬於E
#### 2、圖示

### (四)連通圖
#### 1、連通:無向圖中任兩點都有路經可以到達
#### 2、連通元件:圖形中內的圖形(元件、部分)為連通
#### 3、強連通:有向圖中任兩點都有路經可以到達
#### 4、強連通元件:圖形中內的圖形(元件)皆為強連通【以圖G~3~為例】

### (五)圖形資料抽象型態
【變數設定】for all graph belong to Graph, v1, v2, and v3 belong to Vertices

(1)Graph Create():創造一個空圖
(2)Graph InsertVertex(graph, v1, v2):將點V插入圖形中點(indegree=0)
(3)Graph InsertEdge(graph, v1, v2):加入一個邊在v1,v2之間
(4)Graph DeleteVertex(graph, v):刪除一個點與連接在點上的所有邊。
(5)Graph DeleteEdge(graph, v1, V2)
(6)Boolean isEmpty(graph):前提假設圖等於空回傳True，前提假設不成立則回傳False
(7)List Adjacent(graph, v):回傳所有與V點相連的所有頂點。

### (六)圖形表示方法
#### 以下圖為例

#### 1、相鄰矩陣
x,y軸為各點有邊相連的話則為1(N個點則需準備N^2個位置)

#### 2、相鄰串列
準備一個陣列(n點準備N格)，每個點若有邊相鄰則連結1個Link至該點

#### 3、相鄰多重串列
##### (1)節點結構
##### (2)以G~1~為例
###### 邊名稱 邊的左右2點 討論左點其他連結的邊 討論右點其他連結的邊

### 二、圖形操作
#### (一)深度搜尋
##### 1、程式碼
【類似迷宮走錯退回原位，故使用Stack】
void dfs(int v)
{
node_pointer w;
visited[v] = True;
printf("%5d",v);
for (w = graph[v]; w; w = w ->link)
if(!visited[w->vertex])
dfs(w->vertex);
}
##### 2、時間複雜度分析
###### (1)若使用adjacency lists
則需走訪O(2*e)經過所有點(2為常數)，故時間複雜度為O(e)
###### (2)若使用adjacency matrix
則需走訪(n^2^)格個儲存格，故時間複雜度為O(n^2^)
##### 3、圖例:

##### DFS走訪:
(1) V~0~，V~1~，V~3~，V~7~，V~4~，V~5~，V~2~，V~6~
(2) V~0~，V~2~，V~5~，V~7~，V~4~，V~1~，V~3~，V~6~
(3) V~0~，V~1~，V~4~，V~7~，V~5~，V~2~，V~6~，V~3~
...etc (不唯一)

#### (二)廣度搜尋
##### 1、程式碼
【廣度搜尋以鄰近相連點優先，故使用Queue，先進先出概念，優先拜訪相鄰點】
void bfs(int v)
{
node_pointer w;
queue_pointer front,rear;
front = rear = NULL;
printf("%5d",v);
visited[v] = True;
addq(&front, &rear, v);
while (front)
{
V = deleteq(&front);
for (w = graph[v];
w; w = w->link)
if (!visited[w->vertex])
{
printf("%5d", w->vertex);
addq(&front,&rear,W->vertex);
visited[w->vertex] = true;
}
)
}
##### 2、時間複雜度分析
###### (1)若使用adjacency lists:
每個點都會進入Queue(佇列一次)每次delete都會走訪該點的邊，將邊連有連到的頂點插入佇列中
每個點都走訪連至的邊(2E = degree和)，故時間複雜度為O(2*E)，(2為常數)故為O(E)
###### (2)若使用adjacency matrix:
則需走訪所有儲存空間(n^2^)，故時間複雜度為O(n^2^)
##### 3、圖例:
##### BFS走訪:
(1) V~0~，V~1~，V~2~，V~3~，V~4~，V~5~，V~6~，V~7~
(2) V~0~，V~2~，V~1~，V~5~，V~6~，V~3~，V~4~，V~7~
(3) V~0~，V~1~，V~4~，V~3~，V~2~，V~6~，V~5~，V~7~
...etc (不唯一)

##### (三)連通元件
###### 1、使用DFS or BFS
###### 依G~4~為例為2個連通圖但2圖不相連，故使用BFS or DFS 無法一次拜訪完所有的點，利用此特性，來確認此圖有幾個連通元件。
###### 2、程式碼
void connected (void)
{
int i;
for (i = 0;, i < n; i++)
if(!visited[i])
{
dfs(i);
printf("\n");
}
}
##### 3、時間複雜度分析
###### (1)adjacency lists:
利用DFS需要O(e)的時間，使用迴圈走訪每個點O(n)，故找到所有連通元件需要O(n+e)
###### (2)adjacency matrix:
確認連接的組件需要O(n^2)
##### (四)生成樹
###### 1、圖示(n=4為例)

//Tree不含cycle，邊數 = 頂點數-1


以深度搜尋創造的生成樹稱為深度生成樹
以廣度搜尋創造的生成樹稱為廣度生成樹

###### 2、圖示(深、廣度生成樹)

與BFS和DFS一樣不唯一

##### (五)雙向連接元件與樞紐點
##### 1、樞紐點(Articulation Points)
此點若刪除後導致原圖不連通(變成2個(含)以上的連通元件)，此點稱之樞紐點。
##### 2、雙向連通圖(Biconnected Graph)
途中不含任何樞紐點(EX:cycle)
##### 3、雙向連通元件(Biconnected Components)
圖形中最大的雙聯通圖形
##### 4、圖示:
##### 5、DFS生成樹
dfn(3)=0 【3為起點】 DFS: 3、4、2、1、0、5、6、7、9、8
##### 6、圖示

##### 7、邊的特性
【定義】
未被訪過的點:白色
被拜訪過的點:灰色
已無法再拜訪:黑色

| 邊名稱 | back edge | Tree edge | forward edge | cross edge |
|:------:|:-------------:|:-------------:|:-------------:|:-------------:|
| 特性 | 灰色點→灰色點 | 灰色點→白色點 | 灰色點→黑色點 | 灰色點→黑色點 |
| 無向圖 | 有 | 有 | 沒有 | 沒有 |
| 有向圖 | 有 | 有 | 有 | 有 |

##### //forward edge & cross edge 要區別以發現拜訪時間判斷

##### 8、dfn & low
###### (1)dfn:計算出每個點被追蹤的順序(ex: dfn(a)=3 > dfn(b)=4 故a比b先追蹤)
###### (2)low:計算出此點的子樹沿著backedge所能到達的祖先，最小的dfn值

###### (3)程式碼:
void dfnlow(int u, int v)
{
node_pinter ptr;
int w;
dfn[u]=low[u] = num++;
for(ptr = graph[u]; ptr; ptr = ptr->link)
{
w= ptr->vertex;
if(dfn[w]<0)
{
dfnlow(w,u);
low[u] = MIN2(low[u],low[w]);
}
else if(w != V)
low[u] = MIN2(low[u],dfn[w]);
}
}
##### 9、找出雙連通元件
先判斷樞紐點則可以找到所有雙連通元件
###### 程式碼:
void bicon(int u, int v)
{
node_pointer ptr;
int x,y,z;
dfn[u] = low[u] =num++;
for(ptr = graph[u]; ptr; ptr = ptr->link)
{
w= ptr->vertex;
if (v != w && dfn[w] < dfn[u])
add(&top,u,w);
if(dfn[w]<0)
{
bicon(w,u);
low[u] = MIN2(low[u],low[w]);
if (low[w] >= dfn[u])
{
printf("New biconnected component:");
do
{
delete(&top, &x, &y);
printf("<%d,%d>,x,y");
}
while(!((x == u) && (y ==w)));
printf("\n");
}
}
else if (w != v) low[u] =MIN2(low[u],dfn[w]);
}
}
###### (1)樹根若有2個或以上的子點
###### (2)頂點u非樹根，頂點存在子點v，滿足LOW(v)≧DFN(u)時，頂點u為樞紐點。

### 三、最小成本生成樹(Minmim cost panning trees)
找出最小成本生成樹最常見的3種演算法(Kruskal’s Algo、Prim’s Algo、Soilin’s Algo)，皆為貪婪演算法。
【定義】
1.權重在於邊上
2.使用貪婪演算法(故邊數取最少): 邊數 = 點數-1
3.為樹的型態不含有cycle
#### (一)Kruskal’s Algorithm
##### 1、步驟:
step1:將權重最小的邊加入
step2:檢查是否產生cycle
step3:直到加入n-1條邊結束
##### 2、圖示:
##### 3、程式碼:
T = {};
while (T contains less than n-1 edges && E is not empty)
{
choose a least cost edge (v,w) from E;
delete (v,w) from E;
if ((v,w) does not create a cycle in T)
add (v,w) to T;
else
discard (v,w);
}
if (T contains fewer than n-1 edges)
printf("No spanning tree\n");

#### (二)Prim’s Algorithm
##### 1、步驟:
step1:每次加入一個點至新的集合
step2:找出最小權重的邊加入新的集合
step3:直到新集合內蒐集滿所有點即完成
##### 2、圖示:
##### 3、程式碼:
T ={};
TV = {0};
while (T contains fewer than n-1 edges)
{
let (u, v) be a least cost edge such that u belong to TV and V not belong to TV;
if (there is no such edge)
break;
add v to TV;
add (u, v) to T;
}
if (T contains fewer than n-1 edges)
printf("No spanning tree\n");
#### (三)Soilin’s Algorithm
##### 1、步驟:
step1:視每個點為一個森林
step2:加入每個權重最小的邊，使森林串聯起來(並檢查是否產生cycle)
step3:串聯到只剩一個樹即完成
##### 2、圖示:

### 四、最短路徑
#### (一)單一點至所有點的距離(Single Source All Destinations)
##### 1、Dijkstra's algo
由最近的點開始，依序找出每個點的最短路徑【不允許負邊】【不允許負環】
---
step1: 假設a -> j 路徑長度為10 【2種可能】
【可能一】: 加入新點u, a -> j　仍為最短路徑
【可能二】: 加入新點u, a -> j > a->u->j ,則取代最短路徑
step2: 直到所有點都加入後,即可獲得從a -> j的最短路徑
##### 2、Bellmen's algo
討論起終點最短距離，中間經過1個點、2個點至n-1個點【允許負邊】【不允許負環】
---
step1: 假設a -> j 中間經過1~n-1個點，路徑長度為10 【2種可能】
step2: 選出最短路徑
#### (二)所有點至其他點的距離(All Pairs Shortest Paths)
##### 1、Floyd-Warshall
求任兩點的最短距離【允許負邊】【不允許負環】
將頂點編號討論起終點距離（經過V1、V2....Vn）的距離，選最短路徑
---
step1: 將所有點編號(假設有n個點)
step2: 討論假設a -> j
pass1:可經過V1 最短距離。
pass2:可經過V1、V2最短距離。
...
pass(n-2):可經過V1....Vn-2最短距離。
step3:討論完可經過所有點即為最短距離
##### 2、Johnson's algo
在圖中多加入一個點連至所有點權重為０【允許負邊】【不允許負環】
在使用bellmen'algo，無負邊也可使用Dijkstra's algo
//稀疏矩陣中效果比Floyd-warshall好 O(V*E+V^2logV)

#### (三)遞移包(Transitive Closure)
##### 1、A^+^、A^*^圖示:

###### A^*^ = A^+^ U I

### 五、網絡與拓樸排序
#### (一)點為活動之網絡AOV(Activity On Vertex Networks)
##### 1、定義:
有向圖G其中頂點表示任務或活動，而邊表示任務之間的優先級關係。
##### 2、圖示及表示:
##### 3、拓樸排序:

#### (二)邊為活動之網絡AOE(Activity On Edge (AOE) Networks)
##### 1、條件
(1)邊代表活動且不能有迴圈
(2)單一起終點
##### 2、圖例及表示
##### 3、臨界活動
活動最早開始時間與最晚開始時間一樣的話為關鍵(臨界)活動
關鍵路徑上的所有活動都是關鍵活動，提前完成非關鍵活動（不在關鍵路徑的活動）並不能加快工程的進度。

> 參考資料:Fundamentals of Data Structures in C by Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed