Graph

基本名詞
eulerian path(尤拉路徑),eulerian cycle(尤拉迴路)：從某點出發，每個邊各經過一次，並回到原點
eulerian chain(尤拉串鏈)：從某點出發，每個邊各經過一次即可

由頂點集合(vertex,V)與邊集合(edges,E)組成,因此圖形表示成G=(V,E)
vertex表示成V(G),由頂點組成的集合，不允許空集合
edges表示成E(G),由邊組成的集合，允許空集合

path(路徑)：一組邊所形成
simple path(簡單路徑):路徑中的點只出現一次
相鄰：兩點存在一邊，稱兩點為相鄰
相連通：兩點存在一路徑，稱兩點為相連通
connected graph(連通圖)：任二點都存在一個路徑的圖形，一個圖要連通至少要n-1個邊，若各點互連則邊數(n-1)n/2
connected component(連通單元)：連通圖的子圖
degree(分支度)：點所連接的邊數,對有向圖而言還分in degree進入分支度和out degree離去分支度
weighted graph(加權圖)： 各邊皆有一個加權，表示兩點距離或成本

………………………..

圖形表示法
相鄰矩陣：若有n個點則用n*n的二維矩陣表示，且對角線元素皆為0，若graph[i][j]=1表示點i和點j相連，若為加權圖則1可改成加權值，另外無向圖會對稱，有向圖不一定對稱
若點多邊少，則會成為稀疏矩陣，但若是無向圖則可只儲存對稱的另一邊以節省空間
要找多少邊，是否連通圖，都是big O(N^2)，(因為要在n*n的二維矩陣找)
優點：最簡單安全的表示法
缺點：可能形成一個稀疏矩陣

相鄰串列：n個點的圖用n個鏈結串列表示，而第i個鏈結串列內的各節點＝和第i個點相鄰的各點
對無向圖而言，會有n個起始頂點和2e個串列的節點，而i點的分支度=第i個鏈結串列中節點數
ps,2e個串列的節點:2*邊數=所有串列的節點加總，因為一個邊表示兩點互連，也就表示兩個點分別在自己的鏈結串列各增加一點
ps,當有向圖變為雙向時其實就成為了無向圖
對有向圖而言，會有n個起始頂點和e個串列的節點，而i點的離去分支度=第i個鏈結串列中節點數
若要找出有向圖的進入分支度則要利用反向相鄰串列協助
相鄰串列資料結構：
typedef struct node{
　int vertex;
　int count ;//若要計算該點邊數可加此一變數
　int weight; //若為加權圖可增此欄表示加權值
　struct nextnode *path;
}list;
nextnode headnode[n]; //n＝點數
優點：只表示存在的邊
缺點：存取效率及安全性較差

相鄰多重串列
會有n個起始頂點和e個串列的節點，一個邊用一個節點表示
對無向圖而言，一個節點被二個鏈結串列共用
對有向圖而言，一個節點被一個鏈結串列共用(因為邊具方向性)
優點：每個邊只表示一次
缺點：串列表示最複雜

……………………………

圖的走訪
depth first traversal(深度優先搜尋法):用堆疊處理頂點，以遞迴方式進行走訪
做法：先走訪起始點v，並選與v相鄰且未被走訪的點w，將其視為起始點，遞迴呼叫dfs

虛擬碼：
procedure dfs(v:integer);{
　w:integer;
　visit[v]:=true;write(v); //走訪起始點v，並紀錄點v己走訪
　for(each vertex w屬於neighbor(v))do{ //把每個點v的相鄰點都取出做以下步驟
　　if(not visit[w])then{dfs(w);}
　}
}

若用相鄰矩陣則為bigO(n^2)，演算法為：
void dfs_matrix(int i){ //N,matrix[][],vistied[]為全域
　int k;
　visit(i); //訪問點i
　visited[i]=1; //標示點i己被訪問過
　for(k=0;k < N;k++){
　　if(matrix[i][k]==1 && !visited[k]){dfs_matrix(k);} //若有節點且沒走訪過則進行遞迴
　}
}

若用相鄰串列則為bigO(e)，空間為…
演算法:
void dfs_list(int i){
　nextnode *P; int j;
　visit(i); //訪問點i
　visited[i]=1; //標示點i己被訪問過　
　p=headnode[i].nextnode;
　while(p!=null){
　　j=p->vertex;
　　if(!visited[j]){dfs_list(j);} //若有節點且沒走訪過則進行遞迴
　　else{p=p->nextnode;}
　}
}

…….

breadth first travesal(廣度優先搜尋法):用佇列處理頂點，以迴圈方式進行走訪
做法：
1先走訪起始點v，並將v放入佇列
2從佇列取一點，走訪與該點相鄰且未走過的點放入佇列
重覆2直到佇列為空

虛擬碼：
procedure bfs(v:integer);{
　w:interger;
　q:queue;
　visit(v); visited[v]:=true; //走訪起始點v，並紀錄點v己走訪
　initialqueue(q);
　addqueue(q,v); //將點v放入佇列q
　while not emptyqueue(q)do{
　　deletequeue(q,v); //從佇列q取出點v
　　for(all vertex w屬於neighbor(v))do{ //把每個點v的相鄰點都取出做以下步驟
　　　if not visit[w] then{ //判斷該點是否己走訪
　　　　visit[w]:=true;write(w); //走訪起始點v，並紀錄點v己走訪
　　　　addqueue(q,w); //將點v放入佇列q
　　　}
　　}//for
　}//while
}

若用相鄰矩陣則為bigO(n^2)，演算法：
void bfs_matrix(int i){ //N,matrix[][],vistied[]為全域
　int k;
　visit(i); //訪問點i
　visited[i]=1; //標示點i己被訪問過
　addqueue(q,i);
　while(i=delqueue(q)){
　　for(k=0;k < N;k++){
　　　if(matrix[i][k]==1 && !visited[k]){ //若有節點且沒走訪則做以下
　　　　visit(k);visited[k]=1;addqueue(q,k);
　　　}
　　}
　}
}

若用相鄰串列則為bigO(e),空間為…
演算法:
void bfs_list(int i){
　nextnode *P; int j;
　visit(i); //訪問點i
　visited[i]=1; //標示點i己被訪問過
　addqueue(q,i);//將點i放入佇列
　while(i=delqueue(q)){
　　p=headnode[i].nextnode;
　　while(p!=null){
　　　j=p->vertex;
　　　if(!visited[j]){visit(j);visited[j]=1;addqueue(q,j);} //若有節點且沒走訪過則進行遞迴
　　　else{p=p->nextnode;}
　　}
　}
}

應用：
若可走完所有點，則為連通圖
若不是連通圖，而要決定圖形的所有連通單元，使用相鄰串列複雜度為bigO(n+e)
走訪過程中用到的邊稱為tree edges(樹邊)，其餘的稱為back edges(後邊),若樹含所有點及樹邊則稱為擴張樹

…………

spanning tree(擴張樹)：
最小的連通子圖
說明：一個無向圖，有n個點，n-1個邊，不允許有迴路，(一張n個點的連通圖都存在對應的擴張樹)
the minimun weighted spanning tree(最小成本擴張樹)：在一個加權圖的所有可能擴張樹中，所有邊的加權總和最小的擴張樹

求法：可用kruskal的演算法：此為greedy method，步驟如下：
1由邊集合中找出最小加權邊，
2檢查這個邊 加入tree後是否會形成迴路，若是則捨棄否則保留在tree內
3重覆1，2直到找完所有邊或邊集合為空為止
若用最小堆積結構表示各邊加權，對n個點e個邊的連通圖，則為bigO(e log2(e))

…………

最短路徑：
從點到另一點間所有可能路徑中，所有邊加權總合最小的路徑

從一點到其它所有點的最短路徑與距離
dijkstra的演算法：使用相鄰矩陣則為bigO(N^2)
資料結構：distance[1-n]表示到達點i(起始點)的最短距離(加權)，path[1-n]表示點i(起始點)=點j到點i所達成
演算法：
procedure shortestpath(i){
　for(j:=1 to n)do{distance[j]:=cost[i][j];path[j]:=j}
　visit[i]:=true;
　for(all vertex j屬於neighbor(i))path[j]:=i;
　for(step:=1 to (n-1))do{
　　for(all vertex j屬於not visit[j])choose a vertex K with a minimal distance; //每次執行都是還沒參觀過的點
　　visit[k]:=true; //記在visit內表參觀過
　　for(all vertex j屬於neighbor(k)){ //這裡最多跑n-1次,
　　　new_distance:=distance[k]+cost[k][j];
　　　if(new_distance < istance[j]){
　　　　distance[j]:=new_distance;
　　　　path[j]=k;
　　　}
　　}
　}
}

任意兩點間的最短路徑與距離
重覆執行dijkstra的演算法n次即可，使用相鄰矩陣則為bigO(N^3)
dynamic programming(動態規畫法設計)，可簡單得到，但同樣為bigO(n^3)

……

aov網路(activity on vertex network)
用點表activity工作，邊表工作間處理優先關係的有向圖，因工作間有先後關係所以不能有迴路存在，且擁有topological order(拓樸順序)
topological order ex:若邊為表示必須先做vi才能做vj
用途：應用在有前後線性關性，如表示一個由多個工作所組成的專案的規劃，os表示多個執行的工作元間的等待圖，不能有迴路的組合電路
演算法為先找出進入分支度為0的點

aoe網路(activity on edge network)
臨界工作:工作最早開始時間=工作最晚開始時間
critical path(臨界路徑):起始到結束的頂點皆由臨界工作所組成的路徑
求法：
1先求前進階段在求後退階段，及可得到各點的最早及最晚開始時間
2找出各工作的最早e(ai)與最晚l(ai)開始時間，若相同則為臨界工作

頂點最早與最晚開始時間計算
forward stage(前進階段)：從起始頂點到結束頂點，計算各點最早開始時間，也稱最大階段
求法：設工作ai用兩點表示時，點q的最早開始時間＝點p最早開始時間＋ai長度，若點q有多邊進入則設定其中最大者
backward stage(後退階段)：從結束頂點到起始頂點，計算各點最晚開始時間，也稱最小階段
求法：設工作ai用兩點表示時，點p的最晚開始時間＝點q的最晚開始時間－ai長度，若點p有多邊進入則設定其中最小者

邊(工作)最早e(ai)最晚l(ai)開始時間計算：可由頂點最早e(vi)最晚l(vi)開始時間推導
求法：設工作ai用兩點表示時，e(ai)=點p最早開始時間，l(ai)=點q的最晚開始時間－ai長