《圖說演算法-使用C#》要點摘錄

書名：《圖說演算法-使用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) 便是我們所要求的最短路徑成本矩陣。