图的存储专项
在 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;
}