文章

建图

介绍了图的三种主要建图方法：邻接矩阵、邻接表和链式前向星。每种方法通过示例代码展示如何构建有向图和无向图，适用于不同场景的图算法和数据结构。

发表于 更新于
作者 Sylvan
9 分钟阅读
建图

建图

邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include <iostream>
#include <vector>

using namespace std;

// 点的最大数量
int MAX_N = 11;

// 邻接矩阵方式建图
vector<vector<int>> graph(MAX_N, vector<int>(MAX_N));

// 初始化，下标从 1 开始
void build(int n) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            graph[i][j] = 0;
}

// 有向图建图
void directedGraph(vector<vector<int>> &edges) {
    for (const auto &edge: edges)
        graph[edge[0]][edge[1]] = edge[2];
}

// 无向图建图
void undirectedGraph(vector<vector<int>> &edges) {
    for (const auto &edge: edges) {
        graph[edge[0]][edge[1]] = edge[2];
        graph[edge[1]][edge[0]] = edge[2];
    }
}

void traversal(int n) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            cout << graph[i][j] << " ";
        cout << endl;
    }
}

int main() {
    int n1 = 4;
    vector<vector<int>> edges1 = { {1, 3, 6},
                                  {4, 3, 4},
                                  {2, 4, 2},
                                  {1, 2, 7},
                                  {2, 3, 5},
                                  {3, 1, 1}};
    build(n1);
    directedGraph(edges1);
    traversal(n1);
    cout << endl;
    int n2 = 5;
    vector<vector<int>> edges2 = { {3, 5, 4},
                                  {4, 1, 1},
                                  {3, 4, 2},
                                  {5, 2, 4},
                                  {2, 3, 7},
                                  {1, 5, 5},
                                  {4, 2, 6}};
    build(n2);
    undirectedGraph(edges2);
    traversal(n2);
}

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <iostream>
#include <vector>
#include <forward_list>

using namespace std;

// 点的最大数量
int MAX_N = 11;

// 邻接表方式建图
// 无权
// vector<forward_list<int>> graph(MAX_N);
// 带权
vector<forward_list<pair<int, int>>> graph(MAX_N);

// 初始化，下标从 1 开始
void build(int n) {
    for (int i = 0; i <= n; ++i)
        graph[i].clear();
}

// 有向图建图
void directedGraph(vector<vector<int>> &edges) {
    for (const auto &edge: edges) {
        // edge[0]: u edge[1]: v, u->v
        // edge[2] 为权重
        // forward_list 只能头插，使用 list 可以尾插
        graph[edge[0]].emplace_front(make_pair(edge[1], edge[2]));
    }
}

// 无向图建图
void undirectedGraph(vector<vector<int>> &edges) {
    for (const auto &edge: edges) {
        graph[edge[0]].emplace_front(make_pair(edge[1], edge[2]));
        graph[edge[1]].emplace_front(make_pair(edge[0], edge[2]));
    }
}

void traversal(int n) {
    for (int i = 1; i <= n; ++i) {
        cout << i << "(邻居、边权): ";
        auto it = begin(graph[i]);
        while (it != end(graph[i])) {
            cout << "(" << (*it).first << ", " << (*it).second << ")";
            it++;
        }
        cout << endl;
    }
}

int main() {
    int n1 = 4;
    vector<vector<int>> edges1 = { {1, 3, 6},
                                  {4, 3, 4},
                                  {2, 4, 2},
                                  {1, 2, 7},
                                  {2, 3, 5},
                                  {3, 1, 1}};
    build(n1);
    directedGraph(edges1);
    traversal(n1);
    cout << endl;
    int n2 = 5;
    vector<vector<int>> edges2 = { {3, 5, 4},
                                  {4, 1, 1},
                                  {3, 4, 2},
                                  {5, 2, 4},
                                  {2, 3, 7},
                                  {1, 5, 5},
                                  {4, 2, 6}};
    build(n2);
    undirectedGraph(edges2);
    traversal(n2);
}

链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

#include <iostream>
#include <vector>

using namespace std;

// 点的最大数量
int MAX_N = 11;

// 边的最大数量
// 只有链式前向星方式建图需要这个数量
// 注意如果无向图的最大数量是 m 条边，数量要准备 m*2
// 因为一条无向边要加两条有向边
int MAX_M = 11;

// 链式前向星方式建图
// 下标：顶点编号，值：该顶点第一条边的边号
vector<int> head(MAX_N);
// 下标：边号，值：下一条边的边号
vector<int> nxt(MAX_M);
// 下标：边号，值：去往的顶点编号
vector<int> to(MAX_M);
// 如果边有权重，那么需要这个数组
vector<int> weight(MAX_M);
// 边号计数，从 1 开始，0 表示没有边
int cnt;

// 初始化，下标从 1 开始
void build(int n) {
    // 链式前向星清空
    cnt = 1;
    fill(head.begin(), head.end(), 0);
}

// 链式前向星加边，u->v，w 为权重
void addEdge(int u, int v, int w) {
    // 记录权重
    weight[cnt] = w;
    // 边号为 cnt 的边作为新的头边，插入到旧的头边之前
    nxt[cnt] = head[u];
    to[cnt] = v;
    head[u] = cnt;
    cnt++;
}

// 有向图建图
void directedGraph(vector<vector<int>> &edges) {
    for (const auto &edge: edges)
        addEdge(edge[0], edge[1], edge[2]);
}

// 无向图建图
void undirectedGraph(vector<vector<int>> &edges) {
    for (const auto &edge: edges) {
        addEdge(edge[0], edge[1], edge[2]);
        addEdge(edge[1], edge[0], edge[2]);
    }
}

void traversal(int n) {
    for (int i = 1; i <= n; ++i) {
        cout << i << "(邻居、边权): ";
        for (int ei = head[i]; ei > 0; ei = nxt[ei])
            cout << "(" << to[ei] << "," << weight[ei] << ")";
        cout << endl;
    }
}

int main() {
    int n1 = 4;
    vector<vector<int>> edges1 = { {1, 3, 6},
                                  {4, 3, 4},
                                  {2, 4, 2},
                                  {1, 2, 7},
                                  {2, 3, 5},
                                  {3, 1, 1}};
    build(n1);
    directedGraph(edges1);
    traversal(n1);
    cout << endl;
    int n2 = 5;
    vector<vector<int>> edges2 = { {3, 5, 4},
                                  {4, 1, 1},
                                  {3, 4, 2},
                                  {5, 2, 4},
                                  {2, 3, 7},
                                  {1, 5, 5},
                                  {4, 2, 6}};
    build(n2);
    undirectedGraph(edges2);
    traversal(n2);
}

对比

特性邻接矩阵邻接表（STL）链式前向星
存储结构二维数组向量数组（vector + list）数组模拟链表
空间复杂度O(n²)O(n + m)O(n + m)
适合稠密/稀疏稠密图稀疏图稀疏图
建图复杂度O(m)O(m)O(m)
边权处理简单简单简单
查边是否存在O(1)O(k)，k为出边数O(k)，k为出边数
遍历效率O(n)O(出边数)O(出边数)，cache 友好
插入边O(1)O(1)（vector push_back）O(1)
删除边O(1)O(k)不方便
适合算法Floyd，Prim（稠密）Dijkstra，BFS，DFSDijkstra，SPFA，最大流等
可读性高高中等偏低（更底层）
性能差（空间浪费）一般高（极致优化）

链式前向星性能高在哪

1. 空间连续，缺页率低

  • 链式前向星使用的是连续数组，如 to[], next[], head[]。
  • 遍历一个点的所有出边时，连续访问数组（next 链表本质是数组索引），大幅减少 cache miss。
  • 对比 STL 邻接表（vector 或 list 存储边），后者内存分布不连续，可能频繁访问不同内存页，效率降低。

2. 无动态内存分配，常数小

  • 不用 new、malloc 或 STL 容器的动态扩容机制。
  • 所有数据结构在一开始静态分配，避免堆内存操作，减少碎片和系统开销。
  • 尤其在循环建图、SPFA 这类频繁访问的算法中，常数优化非常明显。

3. 插边操作 O(1)，快且可预测

  • 每次加边就是填一个数组位置，不需要 STL 的函数开销。
  • 常用于静态建图场景（一次性建完不再删改），非常高效。

4. 内存使用更紧凑，Cache 命中率高

  • 所需空间 = O(n + m)，与 STL 相比少了很多额外信息（如 vector 的 capacity、size、指针、对象头等）。
  • 更适合运行在内存受限或对性能极致要求的平台（如竞赛、嵌入式、评测机等）。

5. 便于线性扫描

  • 链式结构可以快速实现边遍历、逆边映射、残量网络更新等操作，尤其适合网络流、最短路等算法。

链式前向星牺牲代码可读性和动态性，换取极致的运行效率和内存利用率，是针对稀疏图算法性能优化的终极手段之一。

algorithm, problems
Algorithm Graph
本文由作者按照 CC BY 4.0 进行授权