Foundations of Graph Theory

Last renew: November 8, 2022 am

图论基础

本质上：图是多叉树的延伸

1
2
3
4
5
6
7
8
9
10
11
// 图的逻辑结构
class Vertex {
	int id;
	Vertex[] neighbors
}

// 多叉树的逻辑结构
class TreeNode {
  int val;
  TreeNode[] children;
}

所以：适用于树的DFS/BFS遍历算法全部适用于图

图的实现方法

一般来说我们很少使用Vertex类来实现图，比较常见的是使用邻接表(Adjacency list)和邻接矩阵(Adjacency matrix)

1
2
3
4
5
6
7
// Adjacency list
// graph[x] store all the adjacent node
List<Integer>[] graph;

// Adjancency matrix
// matrix[x][y] record is there any side in x oriented to y
boolean[][] matrix;

邻接表是一个很直观的表，我们将每个节点的邻居（对于有向图来说是指向的节点/出度）都存到一个列表中，然后将x和这个列表关联起来。

邻接矩阵是一个二位布尔数组，如果节点x和y相连，matrix[x][y]设为true

两种方法的优劣

邻接表：

​ pros: 占用的空间小

​ cons: 无法快速判断两个节点是否相邻

邻接矩阵与上面相反

使用哪一种要看具体情况。

度(degree)

有向图(Oriented graph)的每个节点被分为入度(indegree)与出度(outdegree)

有向加权图

1
2
3
4
5
// Adjancency list
List<int[]>[] graph;

// Adjancency matrix
int[][] matrix;

无向图

很简单，把邻接矩阵中的matrix[x][y]与matrix[y][x]都变成true就可以了，邻接表同理，出度和入度的线全部加入数组即可

图的遍历

数据结构被发明出来无非就是为了遍历和访问 -> 遍历是所有数据结构的基础

图的遍历方法？参考多叉树

1
2
3
4
5
6
7
8
// 多叉树遍历框架
void traverse(TreeNode root) {
  if (root == null) return;
  for (TreeNode child : root.children) {
    traverse(child);
  }
  // post-order
}

但是图可能包含环 (ring)

所以一定需要一个visited[]辅助

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Record the visited node
boolean[] visited;
// Record the path from startPoint (Check is there a exited ring)
boolean[] onPath;

void traverse(Graph graph, int s) {
  if(visited[s]) return;
  visited[s] = true;
  onPath[s] = true;
  for (int neighbor : graph.neighbors(s)) {
    traverse(graph, neighbor);
  }
  // remove the path before
  onPath[s] = false;
}