图的存储专项
在 OI 中,想要对图进行操作,就需要先学习图的存储方式。
在Java中,图的存储方法有多种,具体取决于图的性质和你希望实现的操作。以下是一些常见的图存储方法及其Java实现:
Contents
1. 邻接矩阵(Adjacency Matrix)
邻接矩阵是一种二维数组,用于表示图中顶点之间的连接关系。
public class Graph {
private int[][] adjacencyMatrix;
private int numVertices;
public Graph(int numVertices) {
this.numVertices = numVertices;
adjacencyMatrix = new int[numVertices][numVertices];
}
public void addEdge(int v1, int v2) {
adjacencyMatrix[v1][v2] = 1;
adjacencyMatrix[v2][v1] = 1; // 对于无向图
}
// 其他方法...
}
邻接矩阵只适用于没有重边(或重边可以忽略)的情况。
其最显著的优点是可以 O(1)查询一条边是否存在。
由于邻接矩阵在稀疏图上效率很低(尤其是在点数较多的图上,空间无法承受),所以一般只会在稠密图上使用邻接矩阵
2. 邻接表(Adjacency List)
邻接表使用链表或数组来存储每个顶点的相邻顶点。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Graph {
private int numVertices;
private List<List<Integer>> adjacencyList;
public Graph(int numVertices) {
this.numVertices = numVertices;
adjacencyList = new ArrayList<>(numVertices);
for (int i = 0; i < numVertices; i++) {
adjacencyList.add(new LinkedList<>());
}
}
public void addEdge(int v1, int v2) {
adjacencyList.get(v1).add(v2);
adjacencyList.get(v2).add(v1); // 对于无向图
}
// 其他方法...
}
存各种图都很适合,除非有特殊需求(如需要快速查询一条边是否存在,且点数较少,可以使用邻接矩阵)。
尤其适用于需要对一个点的所有出边进行排序的场合。
4. 邻接表(使用对象)
这种方法类似于邻接表,但使用对象来表示边。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Graph {
private int numVertices;
private List<List<Edge>> adjacencyList;
public Graph(int numVertices) {
this.numVertices = numVertices;
adjacencyList = new ArrayList<>(numVertices);
for (int i = 0; i < numVertices; i++) {
adjacencyList.add(new LinkedList<>());
}
}
public void addEdge(int v1, int v2, int weight) {
adjacencyList.get(v1).add(new Edge(v2, weight));
adjacencyList.get(v2).add(new Edge(v1, weight)); // 对于无向图
}
// 其他方法...
private static class Edge {
int dest, weight;
Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
}
}
这些方法各有优缺点:
– 邻接矩阵:查找边的时间复杂度为O(1),但空间复杂度为O(V^2),其中V是顶点数。
– 邻接表:空间复杂度为O(V+E),其中E是边数。查找边的时间复杂度为O(度数)。
– 边列表:空间复杂度为O(E),适合稀疏图。查找边的时间复杂度为O(E)。
还有一个比邻接矩阵更适合表达稀疏矩阵的结构:
链式前向星(https://zhuanlan.zhihu.com/p/426128224)

链式前向星用一种链表的方式实现了邻接表的存储,并且可以完成简单的出边遍历,所以整体上还是很好用的,如下是一个可靠实现:
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<bool> vis;
vector<int> head, nxt, to;
void add(int u, int v) {
nxt.push_back(head[u]);
head[u] = to.size();//这里利用下标特性,对于u来说存储上一条边的下标就是to的size(),也就是对应下标
to.push_back(v);
}
bool find_edge(int u, int v) {
for (int i = head[u]; ~i; i = nxt[i]) { // ~i 表示 i != -1
if (to[i] == v) {
return true;
}
}
return false;
}
void dfs(int u) {
if (vis[u]) return;
vis[u] = true;
for (int i = head[u]; ~i; i = nxt[i]) dfs(to[i]);
}
int main() {
cin >> n >> m;
vis.resize(n + 1, false);
head.resize(n + 1, -1);
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
add(u, v);
}
return 0;
}