链式前向星
学习前建议学习的前置条件
结构体:
vector邻接表:
链表:
概念
链式前向星与邻接矩阵和邻接表一样, 也是主流的一种存图方式.
它的整体结构很像邻接表, 但是邻接表是线性结构, 链式前向星是链式结构, 实现方式不同, 但是思想是一致的
其实就是链式邻接表, 然后起了一个霸气的名字叫"链式前向星"
为什么使用链式前向星?
链式前向星能做到什么?
答: 链式前向星用途和邻接表相一致.
那么既然他们一样, 我们为什么还要学链式前向星?
我们最先接触到的邻接表写法一般都是vector写法 (可以说这个是最便捷的邻接表, 也最容易理解)
vector 用着一时爽, 但是一旦出现这样的画面时, 是不是开始无从下手了!
内存: vector 是 c++STL 中的 动态连续存储线性表, vector在每次扩充容量时默认都会多申请2倍的空间
时间: STL的调用, 内部实现都导致 vector 是一个非常慢的结构
为了避免手写邻接表这样复杂的操作, 又可以得到一个相对较快, 内存占用较低的方式, 因此我们选择链式前向星
链式前向星存图

对于上面这个无向图, 我们如何通过链式前向星进行存图呢?
这里提供输入格式:每行输入三个值{u, v, w},代表点u连接点v边权(边长)为w
1 2 5 4 1 3 2 4 12 3 4 9 2 3 8
讯享网
模板
以下是链式前向星的一个模板, 下面我们进行逐层分析
讯享网#include<bits/stdc++.h> using namespace std; const int MAXN = ; // 创建边结构 struct Edge{
int v, w, next; // 下一个点,边权,当前边的上一个边 }edge[MAXN*MAXN]; int tot, head[MAXN]; // 建边 void AddEdge(int u, int v, int w) {
// 建边 edge[tot].v = v; edge[tot].w = w; // 连边 edge[tot].next = head[u]; head[u] = tot++; } int main() {
// 初始化head memset(head, -1, sizeof(head)); // 建边 int t; cin >> t; for (int i = 0; i < t; i++) {
int u, v, w; cin >> u >> v >> w; AddEdge(u, v, w); } // 遍历 u 连接的所有边 int u; cin >> u; for (int i = head[u]; i != -1; i = edge[i].next) {
cout << edge[i].v << " " << edge[i].w << endl; } }
一、基本结构
学习链式前向星, 我们首先要了解链式前向星的基本结构
边:
const int MAXN = 10000; // MAXN 表示点的个数 struct Edge{
int v, w, next; }edge[MAXN*MAXN]; // 每个节点最多有n-1条边 int tot; int head[MAXN]; // 头节点数组(存边的下标)
设定Edge结构体表示边的结构
其中 v 代表连接的点(编号), w 代表边的权值, next 代表下一条临接边(边的下标), 而edge数组的下标就代表着边的起点
我们可以与 vector邻接表来对比
讯享网// 边结构 struct Edge {
int v, w; }; vector<Edge>mp[MAXN]; int main() {
int u, v, w; // 存图 while (cin >> u >> v >> w) {
// 无向图, 所以跑两遍 mp[u].push_back({
v, w }); mp[v].push_back({
u, w }); } return 0; }
对比表格
| 含义\结构 | vector邻接表 | 链式前向星 |
|---|---|---|
| 单边的起点 | mp数组的下标 | head的下标 |
| 单边的终点 | Edge中的v | Edge中的v |
| 边权 | Edge中的w | Edge中的w |
| 下一条边下标 | 不需要(直接线性遍历mp[u]) | Edge中的next |
| 起点连接的第一(最后)个边的edge下标 | head的值 |
二、建边
// 建边 void AddEdge(int u, int v, int w) {
// 建边 edge[tot].v = v; edge[tot].w = w; // 连边 edge[tot].next = head[u]; head[u] = tot++; }
链式前向星建边过程展示:
初始化状态:

目标1: 创建一条 1 连 2 长度为 5 的边
- 建边

v = 2(接入点), w = 5(权值), 初始状态没有下一条边, 设为-1

- 连边
head[u] 指向这条边

-----------------------------------------------------------就此第一条边建成----------------------------------------------------------------------
目标2: 在上一条边的基础上, 创建1连4长度为3的边
发现这两条边都是由点1发起的
我们初步设想是这样的效果:

但是很显然这样是行不通的! head[1] 只能存储一个int值, 此时却出现了两个, 怎么办!
此时我们可以将这条边和邻接边连接起来.

- edge[3].next = head[1]; 将edge[3]连接edge[1];
- head[1] = 3; head[1]与edge[1]断开并重新与edge[3]建立连接
最终得到这样的效果

以此类推, 我们便可以完成所有边的连接
三、遍历边
讯享网 // 遍历 u 连接的所有边 int u; cin >> u; for (int i = head[u]; ~i; i = edge[i].next) {
cout << edge[i].v << " " << edge[i].w << endl; }
i 代表着 点u连接的每一条边的下标, 向链表一样, i 通过找到边中的next找到连着的下一条边, 直到找到 -1, 说明找完了
// 遍历 u 连接的所有边 int u; cin >> u; for (int i = head[u]; ~i; i = edge[i].next) {
cout << edge[i].v << " " << edge[i].w << endl; }
i 代表着 点u连接的每一条边的下标, 向链表一样, i 通过找到边中的next找到连着的下一条边, 直到找到 -1, 说明找完了



版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/80744.html