書名：《圖說演算法-使用C#》
作者：吳燦銘、胡昭民
所讀版本：博碩文化
圖形數據表示法
相鄰矩陣法
假設圖有n個頂點，就利用一個n*n的二維矩陣來表示。當A(i, j) = 1，表示圖形中有一條邊(Vi, Vj)存在，反之則沒有。
對無向圖而言，相鄰矩陣必然是對稱的，而且對角線一定為0。有向圖則不一定
在無向圖中，任一節點i的分支度為i列所有元素的和；在有向圖中，節點i的出分支度為i列所有元素的和，入分支度為j行所有元素的和。
相鄰矩陣法需要n^2空間，由於無向圖的相鄰矩陣一定具有對稱關係，所以扣除對角線全部為0外，僅需要儲存上三角形或下三角形的資料即可，因此僅需n(n-1)/2空間
相鄰串列法
將一個n列的相鄰矩陣，表示成n個鏈結串列
鏈結指向其他相連的頂點
在無向圖中，因為對稱的關係，若有n個頂點、m個邊，則形成n個串列首，2m個節點；在有向圖中，則有n個串列首，m個節點
求所有頂點分支的時間複雜度為O(n + m)
相鄰複合串列法
如果處理的是「邊」，則需要使用相鄰複合串列法
節點結構
M：記錄單元 => 該邊是否被找過
V1：邊線起點
V2：邊線終點
Link1：起點指標 => 尚有其他節點與V1相連下，Link1指向下一個與V1相連的節點
Link2：終點指標 => 尚有其他節點與V2相連下，Link2指向下一個與V2相連的節點
索引表格法
以一維陣列依序儲存與各頂點相鄰的所有頂點，並建立索引表格
圖形遍歷法
DFS（深度優先）
結合了遞歸和Stack兩種數據結構的技巧，從圖形的某一頂點開始走訪，被拜訪過的頂點就做上已拜訪的記號，接著走訪此頂點的所有相鄰且未拜訪過的頂點中的任意一個頂點，並做上已拜訪的記號，再以該點為新的起點繼續進行DFS
public class DFSNode
{
public int x;
public DFSNode next;
public DFSNode(int x)
{
this.x = x;
next = null;
}
}
public class GraphLink
{
public DFSNode first;
public DFSNode last;
public bool IsEmpty()
{
return first == null;
}
public void Print()
{
DFSNode curr = first;
while(curr != null)
{
Console.WriteLine(curr.x + " ");
curr = curr.next;
}
Console.WriteLine();
}
public void Insert(int x)
{
DFSNode newNode = new DFSNode(x);
if (this.IsEmpty())
{
first = newNode;
last = newNode;
}
else
{
last.next = newNode;
last = newNode;
}
}
}
public static int[] run = new int[9];
public static GraphLink[] Head = new GraphLink[9];
public static void DFS(int curr)
{
run[curr] = 1;
while(Head[curr].first != null)
{
if(run[Head[curr].first.x] == 0) { DFS(Head[curr].first.x); }
Head[curr].first = Head[curr].first.next;
}
}
static void Main(string[] args)
{
int[,] Data =
{
{ 1, 2 }, { 2, 1 }, { 1, 3 }, { 3, 1 },
{ 2, 4 }, { 4, 2 }, { 2, 5 }, { 5, 2 },
{ 3, 6 }, { 6, 3 }, { 3, 7 }, { 7, 3 },
{ 4, 5 }, { 5, 4 }, { 6, 7 }, { 7, 6 },
{ 5, 8 }, { 8, 5 }, { 6, 8 }, { 8, 6 }
};
for (int i = 1; i < 9; i++)
{
run[i] = 0;
Head[i] = new GraphLink();
for (int j = 0; j < 20; j++)
{
if(Data[j, 0] == i)
{
int num = Data[j, 1];
Head[i].Insert(num);
}
}
Head[i].Print();
}
Console.WriteLine();
DFS(1);
}
BFS（廣度優先）
結合了遞歸和Queue的技巧，從圖形的某一頂點開始走訪，被拜訪過的頂點就做上已拜訪的記號，接著走訪此頂點的所有相鄰且未拜訪過的頂點中的任意一個頂點，並做上已拜訪的記號，再以該點為新的起點繼續進行DFS
public const int MAXSIZE = 10;
static int[] queue = new int[MAXSIZE];
static int front = -1;
static int rear = -1;
public static void Enqueue(int value)
{
if (rear >= MAXSIZE) { return; }
rear++;
queue[rear] = value;
}
public static int Dequeue()
{
if (front == rear) { return -1; }
front++;
return queue[front];
}
public static void BFS(int curr)
{
D_BFSNODE tmpNode;
Enqueue(curr);
run[curr] = 1;
while(front != rear)
{
curr = Dequeue();
tmpNode = Head[curr].first;
while(tmpNode != null)
{
if(run[tmpNode.x] == 0)
{
Enqueue(tmpNode.x);
run[tmpNode.x] = 1;
}
tmpNode = tmpNode.next;
}
}
}
擴張樹
以最小的邊來連結圖形中所有的點，且不造成循環的樹狀結構
當一個圖形連通時，則使用DFS/BFS必能拜訪圖形中所有的頂點，且G=(V,E)的所有邊可分成兩個集合：T和B（T = 搜尋時經過的所有邊，B = 未被經過的邊）。
if S=(V,T)為G中的擴張樹，具有三種性質
E=T+B
加入B中的任一邊到S中，則會產生循環
V中的任何2頂點Vi、Vj在S中存在唯一的一條簡單路徑
使用DFS可產生縱向擴張樹
使用BFS可產生橫向擴張樹
最小花費擴張樹
在樹的邊加上一個權重，使之變成「加權圖形」，如果這個權重代表了頂點間的距離/成本，這類圖形稱為「網絡」
可通過Prim’s演算法或Kruskal’s演算法找到一個無向連通圖形中的最小花費樹
Kruskal’s演算法
將各邊線依權值大小由小到大排列，接著從權值最低的邊線開始架構最小成本擴張樹，如果加入的邊線會造成迴路則捨棄不用，直到加入了n-1個邊線為止。
最短路徑算法
Dijkstra演算法
找到從起點前往各頂點的距離，選擇當中距離最小路徑的頂點並加到集合中。再把起點經過新頂點後，到其他頂點的累計距離進行比較，如果有更小的距離就將路徑更新，然後再選擇距離最小路徑的頂點，如此類推。
A*演算法
Dijkstra演算法的升級版，Dijkstra在尋找最短路徑的過程中，需要實際去計算起點與各頂點的距離。
也就是說，Dijkstra’s演算法在帶有權重的有向圖形間的尋路只是簡單做BFS的工作。
A*結合了在路徑搜尋過程中從起點到各頂點的「實際權重」，及各頂點預估到達終點的「推測權重」
曼哈頓距離
切比雪夫距離
歐氏幾何平面直線距離
主要步驟
決定各頂點到終點的「推測權重」
計算從搜尋完畢的頂點出發到各點的權重，再從中選出一個權重最小的點，再將該點標為搜尋完畢。以此類推，直到終點。
Floyd演算法
A^(k)[i,j] = min{A^(k-1)[i, j], A^(k-1)[i, k] + A^(k-1)[k, j]}, k>=1
k表示經過的頂點，A^(k)[i, j]為從頂點i到j的經由k頂點的最短路徑
A^(0)[i, j] = COST[i, j]（即A^(0) = COST），A^(0)為頂點i到j的直通距離
A^(n)[i, j]代表i 到 j的最短距離，即A^(n) 便是我們所要求的最短路徑成本矩陣。