链式前向星

2018一维 · 2018-11-17 16:09:33 · 个人记录

边的存储

这种存图方式只需要开一个数组存储每个点引出的第一条边，然后存储每个点作为起点的每条边，这样就可以做到不重不漏。

在链式前向星存图中，我们需要定义一个结构体：

struct EDGE 
{
    int next;
    int to;
}edge[1000000];

和一个数组：

int head[1000000];

和一个变量：

int cnt=0;//指针

你会发现竟然没存起点！！其实起点是用head存的

举例：

如图：这样的一个有向图，输入是：

1 2
1 3
1 4
2 3

逐步分析：

1.输入1 2，代表1连向2。

cnt++;//作为结构体下标，没有意义
head[1]=cnt;//结点1的第一个儿子存在了edge[cnt]里面
edge[cnt].to=2;结点1的儿子是2

此时：

2.输入1 3，代表1连向3。

cnt++;
head[1]=cnt;
edge[cnt].to=3;结点1的儿子是3
//这时,3成为了结点1的儿子，不过2被挤了下去...
//所以要引入结构体中next元素，记录：3还有个兄弟（next）是2
//所以代码要换成：
cnt++;
edge[cnt].to=3;//结点1连向3
edge[cnt].next=head[1];//3的兄弟是2
head[1]=cnt;//更新head

此时：

3.输入1 4，代表1连向4。

此时：

4.输入2 3，代表2连向3。

此时：

注意：edge[cnt].next 和head[1]存贮的都是结构体下标（即cnt的值）若要访问指向的边的编号，分别用edge[edge[cnt].next].to，edge[head[1]].to

若需要记录权值，在结构体中加入一个元素即可

代码：(带权值）

#include<iostream>
using namespace std;
struct edge 
{ 
    int next;
    int to;
    int wei;
}edge[MAXM];
int head[MAXN];//head[i]为i点的第一条边
int cnt=0;
void addedge(int u,int v,int w) //起点，终点，权值 
{
    edge[++cnt].next=head[u];//更新cnt
    edge[cnt].to=v;
    edge[cnt].w=w;
    head[u]=cnt;
}
int main()
{
    int n;
    for(int i=1;i<=n;i++)
    {
        int a,b,wei;
        addedge(a,b,wei);
        //如果是无向图，还要addedge(b,a,wei);
    }
}

注意：

这里的next指的是遍历时的下一条边，head指的是遍历时的第一条边，而存边时相当于反过来操作，所以next记录上一条边，而head记录最后一条边。

边的遍历

在遍历以x为起点的所有边时，只需要这样就行

    for(int i=head[x];i!=0;i=edge[i].next)

这个循环的结束条件是i等于0，因为最后一条边，也就是存边时第一条边，在把head值存进next时，head还没有更新过，也就是0。所以当next返回0时，就说明这些边遍历完毕了。

优势与特点

既可以存图，也可以存树，比起邻接矩阵，链式前向星的空间复杂度是O（n），大大节省了存储空间，因为按边存储省掉了很多两点无边的空间。并且在遍历的时候，那些与起点无边相连的点也不需要进行处理，可以说时间和空间都占优势，这就是被OIer们广泛使用的原因。

补充+重点

（2019/1/15update）

 void addedge(int u,int v,int w) //起点，终点，权值 
{
    edge[++cnt].next=head[u];//更新cnt
    edge[cnt].to=v;
    edge[cnt].w=w;
    head[u]=cnt;
}

这个代码中，cnt代表边的编号。

如果cnt初始值赋为1,存的是无向图，那么：

边cnt的反向边是cnt^1