当前位置：首页 > news >正文

链式前向星（最通俗易懂的讲解）

news 2025/5/11 7:15:39

链式前向新：用于存储图的边集数组

前言

当我们存储图的时候，往往会使用邻接矩阵或是邻接表。

邻接矩阵好写，但太浪费空间，节点一多就存不下；

邻接表效率高，但涉及指，不好写容易出错；用 vector 又可能超时。

链式前向星就是一个相对中庸的存储方式，虽然说，链式前向星使用并不广泛，但在需要使用复杂邻接表时，这就是一个较好的选择。

链式前向星其实就是静态建立的邻接表，时间复杂度为O(m)，空间复杂度也为O(m)。

思想

对于下图：

图1

输入为：

5 7

1 2 3

2 3 1

1 3 4

1 5 3

4 1 5

4 5 1

3 4 2

我们将起点都是 from 的边串在一起，用 head[from] 存储头节点（见图2，下图为最终形式）

图2

具体插入操作与链表相似（见图3）

图3

代码与运行结果

里有注释，慢慢理解

#include <iostream>
#include <cstring>using namespace std;const int N = 2e2 + 5, M = 1e3 + 5;int n, m, cnt; //n个点，m条边
struct Edge {int to, value, next;//终点，边权，同起点的上一条边的编号
} edge[M]; //边集
int head[N]; //head[i] 表示以 i 为起点的第一条边在边集数组的位置（编号）void add_edge(int from, int to, int value) { //u起点，v终点，w边权edge[++ cnt] = {to, value, head[from]}, head[from] = cnt;// 赋终点权值 并且将新的节点赋在头上	更新头
}int main() {cin >> n >> m;/* 初始化 */cnt = 0;memset(head, -1, sizeof head);/* 加边 */for (int i = 1; i <= m; i ++) { //输入m条边int a, b, c;cin >> a >> b >> c;add_edge(a, b, c);}/* 遍历 */for (int i = 1; i <= n; i ++) {cout << ">" << i << "\n";bool hase = false;for (int j = head[i]; j != -1; j = edge[j].next) //遍历以i为起点的边cout << i << " " << edge[j].to << " " << edge[j].value << "\n", hase = true;if (!hase)cout << "nothing\n"; //第i个节点没有出去的边}return 0;
}
/*
5 7
1 2 3
2 3 1
1 3 4
1 5 3
4 1 5
4 5 1
3 4 2
*/

可以注意到 head 的初始值为 -1

这使得 head[i] 中第一个边的 next 为 -1，这正作为链的结尾（见图3

所以当访问指针 ( j ) 为 -1 时，就代表访问结束了

运行结果参考

图4