邻接矩阵

使用于边数较多的稠密图

1
2
3
4
5
6
7
// 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
int[][] w = new int[N][N];

// 加边操作
void add(int a, int b, int c) {
    w[a][b] = c;
}

邻接表

与数组存储单链表的实现一致（头插法），又称链式前向星存图，适用于边数较少的稀疏图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
int idx;

// 初始化
Arrays.fill(he, -1);

// 建图
void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = he[a];
    he[a] = idx;
    w[idx] = c;
    idx++;
}

其中，N为节点个数，M为边的个数

  • he数组：存储是某个节点所对应的边的集合（链表）的头结点；
  • e数组：存储访问某一条边指向的节点；
  • ne数组：用于找到下一条边；
  • w数组：用于记录某条边的权重

当我们想遍历由a点出发的边时，可以使用如下方法：

1
2
3
for (int i = he[a]; i != -1; i = ne[i]) {
    int b = e[i], c = w[i]; // 存在由 a 指向 b 的边，权重为 c
}

邻接表(Map实现)

仅适用于无权图

1
2
3
4
5
6
7
8
9
10
11
12
13
Map<Integer, List<Integer>> adj = new HashMap<>();

// 建图
void add(int a, int b) {
    adj.computeIfAbsent(a, key -> new ArrayList<>()).add(b);
}

// 遍历
List<Integer> list = adj.get(node);
if (list == null) return;
for (Integer i : list) {
    ...
}

类

这是一种最简单，但是相比上述两种存图方式，使用得较少的存图方式。

只有当我们需要确保某个操作复杂度严格为$O(M)$时，才会考虑使用。

1
2
3
4
5
6
7
class Edge {
    // 代表从 a 到 b 有一条权重为 c 的边
    int a, b, c;
    Edge(int _a, int _b, int _c) {
        a = _a; b = _b; c = _c;
    }
}

通常我们会使用 List 存起所有的边对象，并在需要遍历所有边的时候，进行遍历：

1
2
3
4
5
6
7
List<Edge> es = new ArrayList<>();

...

for (Edge e : es) {
    ...
}