图论——链式前向星

整理自: https://blog.csdn.net/qq_35501306/article/details/106276964

链式前向星概括

以同起点为一条链, 数组 $head[a]$ 存储起点 $a$ 的最新录入的一条边的索引, 每条边以结构体的形式存储该边信息 (该边终点, 权值, 同起点的边中的上一条边即上一次录入的边的位置), 所有边构成一个结构体数组.

很多帖子说到的是存储的是下一条边, 这种理解很容易给人误导, 应该是每一条边都能通过自身结构体存储的信息回溯到上一条边, 所以叫前向星.

假如我们要找出一条 $a \rightarrow b$ 的边, 先根据 $head[a]$ 找出从起点 $a$ 出发的所有边里最新录入的那条边, 然后根据该边找出它的上一条边, 再根据上一条边找出它的上上一条边, 直到找到一条终点为 $b$ 的边为止. 整个过程是链式回溯的, 所以是链式前向星.

链式前向星范例

边的录入顺序 (起点 $a \rightarrow 终点 b = 权值 w$):

第 $0$ 条边: $5 \rightarrow 3 = 1$, 此时 $head[5]=0$ 以 $5$ 为起点没有上一条边
第 $1$ 条边: $1 \rightarrow 2 = 9$, 此时 $head[1]=1$ 以 $1$ 为起点没有上一条边
第 $2$ 条边: $3 \rightarrow 5 = 11$, 此时 $head[3]=2$ 以 $3$ 为起点没有上一条边
第 $3$ 条边: $2 \rightarrow 1 = 5$, 此时 $head[2]=3$ 以 $2$ 为起点没有上一条边
第 $4$ 条边: $4 \rightarrow 5 = 6$, 此时 $head[4]=4$ 以 $4$ 为起点没有上一条边
第 $5$ 条边: $3 \rightarrow 1 = 7$, 此时 $head[3]=5$ 以 $3$ 为起点的上一条边的是第 $2$ 条边
第 $6$ 条边: $3 \rightarrow 4 = 4$, 此时 $head[3]=6$ 以 $3$ 为起点的上一条边的是第 $5$ 条边
第 $7$ 条边: $4 \rightarrow 1 = 2$, 此时 $head[4]=7$ 以 $4$ 为起点的上一条边的是第 $4$ 条边

假如我们要找 $3 \rightarrow 5$ 这条边:

根据 $head[3]=6$, 得到起点 $3$ 的最新一条录入的边是第 $6$ 条边
根据 $edge[6].to=4$, 这条是 $3 \rightarrow 4$ 的边, 不符合, 我们继续找
根据 $edge[6].pre=5$, 得到第 $6$ 条边的上一条同起点边是第 $5$ 条边
根据 $edge[5].to=1$, 这条是 $3 \rightarrow 1$ 的边, 不符合, 我们继续找
根据 $edge[5].pre=2$, 得到第 $5$ 条边的上一条同起点边是第 $2$ 条边
根据 $edge[2].to=5$, 这条是 $3 \rightarrow 5$ 的边, 找到了

链式前向星实现

具体实现

边的结构体定义, 存储该边信息

struct Edge{
    int to;  // 表示该边的终点
    int pre; // 同起点的上一条边的位置, 值为-1 表示没有上一条边
    int w;   // 该边权值
};

定义链头 $head$, 存储每个起点的最新一条边的索引, $-1$ 表示该点无边

int head[n+1];
memset(head,-1, sizeof(head));

定义结构体数组 $edge$, 存储每一次录入的边

Edge edge[2*m+2];

定义一个边的计数器 $ecnt$, 表示当前已录入边的数量

int ecnt=0;

增边函数, 增加一条 $a \rightarrow b$ 的权值为 $w$ 的边

inline void addEdge(int a, int b, int w, int head[], Edge edge[], int &ecnt){
    edge[ecnt].w=w;
    edge[ecnt].to=b;
    edge[ecnt].pre=head[a];   //该边上浮为起点 a 的所有边里最新的边
    head[a]=ecnt++;
}

无向图的存储

addEdge(a, b, w, head, edge, ecnt);
addEdge(b, a, w, head, edge, ecnt);

每次加边的时候都需要反向加边.

完整代码

//
// Created by duhbb on 2022/10/12.
//
#include<iostream>
#include<fstream>
#include<cstring>

using namespace std;

// 边的结构体定义
struct Edge {
    int to;  // 表示该边的终点
    int pre; // 同起点的上一条边的位置, 值为 -1 表示没有上一条边
    int w;   // 该边权值
};

//增加一条 a -> b 的权值为 w 的边
inline void addEdge(int a, int b, int w, int head[], Edge edge[], int &ecnt) {
    edge[ecnt].w = w;
    edge[ecnt].to = b;
    edge[ecnt].pre = head[a];//该边上浮为起点 a 的所有边里最新的边
    head[a] = ecnt++;
}

int main() {
    ifstream ifs("./链式前向星-input.txt");
    int n, m;//n 表示顶点数, m 表示边数
    ifs >> n >> m;

    //初始化
    //head[a]表示顶点 a 的最新一条边的数组下标,-1 表示该点无边
    int head[n + 1];
    memset(head, -1, sizeof(head));
    Edge edge[2 * m + 2];
    //当前已录入边的数量
    int ecnt = 0;

    for (int i = 0; i < m; i++) {
        int a, b, w;//边 a 到边 b 的权值 w
        ifs >> a >> b >> w;
        addEdge(a, b, w, head, edge, ecnt);
        //无向图, 每次都需要反向加边
//      addEdge(b, a, w, head, edge, ecnt);

//      //调试用, 输出有向图每条边的情况
//      cout<<" 第"<<i<<" 条边:"
//      <<a<<" -> "<<edge[i].to<<" = "<<edge[i].w
//      <<"\t 此时 head["<<a<<"]="<<head[a]
//      <<"\t 以"<<a<<" 为起点";
//      if(edge[i].pre==-1)
//          cout<<" 没有上一条边";
//          else
//              cout<<" 的上一条边是第"<<edge[i].pre<<" 条边";
//      cout<<endl;

//      //调试用, 输出无向图每条边的情况
//      cout<<" 第"<<2*i<<" 条边:"
//      <<a<<" -> "<<edge[2*i].to<<" = "<<edge[2*i].w
//      <<"\t 此时 head["<<a<<"]="<<head[a]
//      <<"\t 以"<<a<<" 为起点";
//      if(edge[2*i].pre==-1)
//          cout<<" 没有上一条边";
//          else
//              cout<<" 的上一条边是第"<<edge[2*i].pre<<" 条边";
//      cout<<endl;
//
//      cout<<" 第"<<2*i+1<<" 条边:"
//      <<b<<" -> "<<edge[2*i+1].to<<" = "<<edge[2*i+1].w
//      <<"\t 此时 head["<<b<<"]="<<head[b]
//      <<"\t 以"<<b<<" 为起点";
//      if(edge[2*i+1].pre==-1)
//          cout<<" 没有上一条边";
//          else
//              cout<<" 的上一条边的是第"<<edge[2*i+1].pre<<" 条边";
//      cout<<endl;
    }
    ifs.close();
    //遍历输出, 有向图和无向图均适用
    for (int a = 1; a <= n; a++) {//起点 a
        cout << a;
        for (int b = head[a]; b != -1; b = edge[b].pre) {//终点 b

            cout << " -> " << edge[b].to;
        }
        cout << endl;
    }
    return 0;
}

样例输入

有向图

无向图

样例输出

有向图

无向图

重边的处理 (待补充)

链式前向星+Prim 算法 (待补充)

链式前向星优缺点

优点

内存利用率高: 可以准确开辟最多边数的内存, 不像邻接表有爆内存的风险.
对不确定边的操作方便效率也不错, 这点和邻接表一样, 不会遍历到不存在的边.
几乎可以用于全部的图论题目

缺点

难于理解, 代码较复杂
重边不好处理, 这点与邻接表一样, 只有通过遍历判重.
对确定边的操作效率不高, 也与邻接表一样, 不能通过两点马上确定边, 只能遍历查找.