图的存储

1. 邻接矩阵

思想：

• 利用二维数组 g[N][N] 存储所有点到点的权值。
  • 其中 N 为点的数量，g[i][j] 表示点 i 到点 j 的权值。

时间复杂度： \(\mathcal{O}(n^2)\)

空间复杂度： \(\mathcal{O}(n^2)\)

应用：

• 仅在点数不多的稠密图中使用。
  • 大部分情况下点的数量 \(n=10^3\)，边的数量 \(m=10^6\)。

示例：

• 现有 n 个点共 m 条边，以及每条边的起始点、终点及权值。
  • 这些点和边共同构成一个有向图。
  • 存储这些信息并输出。

输入：

4 5
1 2 20
1 4 40
2 3 50
2 4 60
3 2 30

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1010; // 图的大小

int n, m;
int g[N][N];
bool vis[N]; // 标记是否走过

void dfs(int u) { // 深度优先遍历
    vis[u] = 1; // 标记当前点已经遍历过
    for (int i = 1; i <= n; i++) { // 遍历n个点
        if (g[u][i] != 0) {
            cout << u << ' ' << i << ' ' << g[u][i] << endl;
            if (vis[i]) continue; // 当前的边的终点已经走过则跳过
            dfs(i);
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = c;
        // g[b][a] = c; // 如果是无向图加一条边
    }
    dfs(1); // 从1号点开始遍历
}

int main() {
    solve();
    return 0;
}

输出：

1 2 20
2 3 50
3 2 30
2 4 60
1 4 40

---

2. 边集数组

思想：

• 利用结构体数组 e[N] 存储边的信息。
  • 其中 e[i] 包含第 i 条边的 {起始点 u, 终点 v, 边权 w}。

时间复杂度： \(\mathcal{O}(nm)\)

空间复杂度： \(\mathcal{O}(m)\)

应用：

• 在 Kruskal 算法中，需要将边按照边权排序，适合直接存边。

示例：

• 现有 n 个点共 m 条边，以及每条边的起始点、终点及权值。
  • 这些点和边共同构成一个有向图。
  • 存储这些信息并输出。

输入：

4 5
1 2 20
1 4 40
2 3 50
2 4 60
3 2 30

代码：

#include <bits/stdc++.h>
using namespace std;

const int M = 1000010; // 边的数量

struct Edge {
    int u, v, w;
} e[M];

int n, m;

void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    for (int i = 0; i < m; i++) {
        cout << e[i].u << ' ' << e[i].v << ' ' << e[i].w << endl;
    }
}

int main() {
    solve();
    return 0;
}

输出：

1 2 20
1 4 40
2 3 50
2 4 60
3 2 30

---

3. 邻接表

思想：

• 利用出边数组 e[N] 存储边的信息。
  • 其中 e[u] 是一个数组（或向量），存储从点 u 出发的所有边，边的信息包含 {终点 v, 边权 w}。

时间复杂度： \(\mathcal{O}(n+m)\)

空间复杂度： \(\mathcal{O}(n+m)\)

应用：

• 可以应用于各种图，但在网络流等需要反向边的场景中需额外处理。

示例：

• 现有 n 个点共 m 条边，以及每条边的起始点、终点及权值。
  • 这些点和边共同构成一个有向图。
  • 存储这些信息并输出。

输入：

7 6
4 3 90
1 4 30
5 7 80
5 6 60
1 5 20
5 2 70

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1010; // 图的大小

int n, m;

struct edge {
    int v, w;
};

vector<edge> e[N]; // 邻接表，e[u]存储所有从u出发的边

void dfs(int u, int fa) { // 深度优先遍历，fa记录当前点的父节点
    for (auto p : e[u]) { // 遍历所有的出边
        if (fa == p.v) continue; // 若该出边的终点是父节点，说明已经走过
        cout << u << ' ' << p.v << ' ' << p.w << endl;
        dfs(p.v, u);
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        e[a].push_back({b, c});
        // e[b].push_back({a, c}); // 如果是无向图，就加一条反向边
    }
    dfs(1, 0); // 从1号点开始遍历
}

int main() {
    solve();
    return 0;
}

输出：

1 4 30
4 3 90
1 5 20
5 7 80
5 6 60
5 2 70

---

4. 链式前向星

思想：

• 利用边集数组 e[N] 存储所有边的信息，表头数组 h[N] 存储每个顶点的第一条出边的编号。
  • 其中 e[i] 存储第 i 条边的 {终点 v, 边权 w, 下一条边的编号 ne}，h[u] 存储顶点 u 的第一条出边的编号。

时间复杂度： \(\mathcal{O}(n+m)\)

空间复杂度： \(\mathcal{O}(n+m)\)

应用：

• 适用于有向图、无向图等多种图结构，并支持快速访问反向边。

示例：

• 现有 n 个顶点共 m 条边，以及每条边的起点、终点及权值。
  • 这些点和边共同构成一个无向图。
  • 存储这些信息并输出。

输入：

6 5
4 3 90
1 4 30
5 6 60
1 5 20
5 2 70

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1010; // 图的大小
const int M = 100010; // 边的数量

int n, m;

struct edge {
    int v, w, ne; // 终点，边权，下一条边的编号
} e[M]; // 边集数组

int idx, h[N]; // idx为当前边的编号，h[u]存储顶点u的第一条出边的编号

// 添加一条从a到b，权值为c的边
void add(int a, int b, int c) {
    e[idx] = {b, c, h[a]};
    h[a] = idx++;
}

// 深度优先遍历，fa为当前节点的父节点，防止走回头路
void dfs(int u, int fa) {
    for (int i = h[u]; ~i; i = e[i].ne) { // ~i 等价于 i != -1
        if (fa == e[i].v) continue;
        cout << u << ' ' << e[i].v << ' ' << e[i].w << endl;
        dfs(e[i].v, u);
    }
}

void solve() {
    cin >> n >> m;
    memset(h, -1, sizeof h); // 初始化表头数组，-1表示空链表
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c); // 无向图，双向加边
    }
    dfs(1, 0); // 从1号顶点开始遍历，0为虚拟父节点
}

int main() {
    solve();
    return 0;
}

输出：

1 5 20
5 2 70
5 6 60
1 4 30
4 3 90

---

5. 总结

• 链式前向星是解决图论问题的强大工具。
  • 它建图简便，空间利用率高（\(\mathcal{O}(n+m)\)），遍历边的效率高，在算法竞赛中被广泛推荐使用。