2025-09-04

图的存储专项

在 OI 中，想要对图进行操作，就需要先学习图的存储方式。

在Java中，图的存储方法有多种，具体取决于图的性质和你希望实现的操作。以下是一些常见的图存储方法及其Java实现：

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

using namespace std;

int n, m; vector vis; vector 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; }