2025年链式前向星

链式前向星链式前向星 学习前建议学习的前置条件 结构体 vector 邻接表 链表 概念 链式前向星与邻接矩阵和邻接表一样 也是主流的一种存图方式 它的整体结构很像邻接表 但是邻接表是线性结构 链式前向星是链式结构 实现方式不同 但是思想是一致的 其实就是链式邻接表 然后起了一个霸气的名字叫 链式前向星 为什么使用链式前向星

大家好,我是讯享网,很高兴认识大家。

链式前向星

学习前建议学习的前置条件

结构体:
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 的边

  1. 建边

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

在这里插入图片描述

  1. 连边

    head[u] 指向这条边

在这里插入图片描述

-----------------------------------------------------------就此第一条边建成----------------------------------------------------------------------

目标2: 在上一条边的基础上, 创建1连4长度为3的边

发现这两条边都是由点1发起的

我们初步设想是这样的效果:

在这里插入图片描述

但是很显然这样是行不通的! head[1] 只能存储一个int值, 此时却出现了两个, 怎么办!

此时我们可以将这条边和邻接边连接起来.

在这里插入图片描述

  1. edge[3].next = head[1]; 将edge[3]连接edge[1];
  2. 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, 说明找完了

小讯
上一篇 2025-03-28 11:14
下一篇 2025-01-05 22:31

相关推荐

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