Graph - 图

图的表示通常使用邻接矩阵和邻接表，前者易实现但是对于稀疏矩阵会浪费较多空间，后者使用链表的方式存储信息但是对于图搜索时间复杂度较高。

编程实现

邻接矩阵

设顶点个数为 V, 那么邻接矩阵可以使用 V × V 的二维数组来表示。
g[i][j]表示顶点i和顶点j的关系，对于无向图可以使用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];

邻接表

邻接表通过表示从顶点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. }

无向图同上，只不过在建图时双向同时加。

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. }