Graph - 圖

圖的表示通常使用鄰接矩陣和鄰接表，前者易實現但是對於稀疏矩陣會浪費較多空間，後者使用鏈表的方式存儲資訊但是對於圖搜索時間複雜度較高。

程式實現

鄰接矩陣 (Adjacency Matrix)

設頂點個數爲 V, 那麼鄰接矩陣可以使用 V × V 的二維陣列來表示。
g[i][j]表示頂點i和頂點j的關係，對於無向圖(undirected graph)可以使用0/1表示是否有連接，對於帶有權重的圖則需要使用INF來區分。有重邊時保存邊數或者權值最大/小的邊即可。

Python

  1. g = [[0 for _ in range(V)] for _ in range(V)]

Java

  1. /* Java Definition */
  2. int[][] g = new int[V][V];

C++

  1. vector<vector<int>> g (V, vector<int>(V, 0));

鄰接表 (Adjacency List)

鄰接表通過表示從頂點i出發到其他所有可能能到的邊。

有向圖

Python

  1. class DirectedGraphNode:
  2.     def __init__(self, x):
  3.         self.label = x
  4.         self.neighbors = []

Java

  1. /* Java Definition */
  2. class DirectedGraphNode {
  3.     int label;
  4.     ArrayList<DirectedGraphNode> neighbors;
  5.     DirectedGraphNode(int x) {
  6.         label = x;
  7.         neighbors = new ArrayList<DirectedGraphNode>();
  8.     }
  9. }

C++

  1. struct DirectedGraphNode {
  2.     int label;
  3.     vector<DirectedGraphNode*> neighbors;
  5.     DirectedGraphNode(int x): label(x) { }
  6. };

無向圖同上，只不過在建圖時雙向同時加。

Python

  1. class UndirectedGraphNode:
  2.     def __init__(self, x):
  3.         self.label = x
  4.         self.neighbors = []

Java

  1. class UndirectedGraphNode {
  2.     int label;
  3.     ArrayList<UndirectedGraphNode> neighbors;
  4.     UndirectedGraphNode(int x) {
  5.         this.label = x;
  6.         this.neighbors = new ArrayList<UndirectedGraphNode>();
  7.     }
  8. }

C++

  1. struct UndirectedGraphNode {
  2.     int label;
  3.     vector<UndirectedGraphNode*> neighbors;
  5.     UndirectedGraphNode(int x): label(x) { }
  6. };