一篇博客弄清链式前向星原理+建图遍历模板

链式前向星,就是依靠存储边来存储图的,适合用来优化DFS、BFS、SPFA这些算法(当图比较稀疏时,如果接近完全图时则不能使用).

我们先来看链式前向星节点的构建,假设有一条从1到2的边,边长为3

struct node
{
    int w,v,next;
}edge[maxn];
int cnt;
int head[maxn];

w 表示边的权重3
v 表示这条边通向的节点2
next 是下一条源点为1的边在数组中存放的位置,为0则说明没有了
cnt 就是一个指针,指向下一个要存放边的位置
head[1] 指1号点为起点最后一条存放的边

是不是太抽象了?那我们来举一个例子.

画图工具:点击这里

[egin{array}{ccccccc}{下标}&{1} & {2} & {3} & {4} & {5} & {6} & {7} \ {u}&{1} & {2} & {3} & {4} & {1} & {1} & {4} \ {v}&{2} & {3} & {4} & {5} & {3} & {5} & {1} \ {next}&{0} & {0} & {0} & {0} & {1} & {5} & {4}end{array} ]

[egin{array}{ccccccc} {下标}&1&2&3&4&5\ {head}&6&2&3&7&0\ end{array} ]

那么这就是数组中存放的内容了(实际上没有(u)这一行),可以看到前向星的遍历都是从后放入的边遍历向先放入的边,一开始放入的边next都为0.所以假设已经有1->2这条边时,再加入1->3,head[1]=1,所以遍历完1->3之后就要去遍历1->2,1->3的next就为1,然后head[1]变为cnt,cnt++就完事了,下一个来的边1->5的next便可以立即指向1->3的位置.

需要遍历某个点的所有邻边时,只需要使用for( int i=head[u]; i!=0; i=edge[i].next )即可.

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node
{
    int w,v,next;
}edge[maxn];
int cnt;
int head[maxn];
void addEdge(int u,int v,int w=0)
{
    edge[cnt].w=w;
    edge[cnt].v=v;
    edge[cnt].next=head[u];//head[u]表示以u为起点最后一次存储的位置
    head[u]=cnt++;
}
int main()
{
    memset(head,0,sizeof(head));
    cnt=1;
    int n;
    cin>>n;
    int a,b;
    while(n--)
    {
        cin>>a>>b;
        addEdge(a,b);
    }
    //
    for(int i=head[1];i!=0;i=edge[i].next)
    {
        cout<<edge[i].v<<endl;
    }
}

输出

7
1 2
2 3
3 4
4 5
1 3
1 5
4 1
5
3
2

Process returned 0 (0x0)   execution time : 1.713 s
Press any key to continue.

一篇博客弄清链式前向星 原理+建图遍历模板

Code

一篇博客弄清链式前向星原理+建图遍历模板