链式前向星存图(有图详解)

链式前向星:既然是链式那么肯定和链表相关,前向星是每次指向都向前

链式前向星存图是以边为中心,并不是以结点为中心,它记录的是边的一些属性,包括边边的id、头节点、尾结点、权值、边的指向!

边的指向是遍历图的时候需要按照一定顺序去遍历,而不能胡乱的去遍历,那么就需要这些边存在一定规律,所以用到"边的指向",这个指向是相同头节点出发,依次指向相同头节点的边,下图为例。

通过这幅图我们可以看到v1、v2、v3、v4都是由结点u出发,引出的边1、边2、边3、边4,可以看到橙色的指向箭头,边4指向边3、边3指向边2、边2指向边1、边1指向null。

如何通过代码实现呢?

我们可以看到一个结构体struct可以存 头节点u、尾结点v、权值w、指向next,但是我们如何通过结点u拿到最后一个条边呢?(因为遍历的时候一定要以边为中心进行遍历,所以肯定要找出一条边作为头,依次去遍历), 在这里我们用一个head数组存放以u为头节点,最后一条边的编号id,这样就可以通过head数组head[u]找到最后一条边的编号,通过边的next指向,依次去遍历,直到next==null, 一个u结点是这样遍历出所有以u为头节点的边的,那么我们遍历所有的结点,不就可以遍历出所有的边了嘛!

常用代码模板

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn=1e6+10;
int n,ecnt;//ecnt统计一共有多少条边

int head[maxn];//存放以u为头节点的最后一条边的编号
struct edge
{
    int u,v,next; //结构体表示边
} E[maxn];

void add(int u,int v)
{
    E[++ecnt].u=u; //从1开始为边进行编号
    E[ecnt].v=v;
    E[ecnt].next=head[u];//因为head[u]每次存放最后一条边的编号,所以新建的边要指向head[u]
    head[u]=ecnt;//更新head[u],当前边为最新需要下一条边指向的边
}



int main()
{

    cin>>n;

    int u,v;
    for(int i=1; i<=n-1; i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        //add(v,u); 双向边则添加两条
    }
    
    for(int i=1; i<=n; i++)
    {
        if(head[i]!=0)
        {   //取到最后一条边进行遍历  
            for(int edge=head[i]; edge!=0; edge=E[edge].next)
            {
                cout<<E[edge].u<<"-----"<<E[edge].v<<endl;
            }
        }
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

以这样一副树进行遍历

打印结果

我们也可以利用深搜dfs来进行遍历 大概模版如下

void dfs(int u)
{

    for(int i=head[u]; i; i=E[i].next)
    {
        int v=E[i].v;
        if(!vis[v])
        {
            vis[v]=1;
            dfs(v);//深搜dfs遍历
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

感谢观看,多多点赞支持