链式前向星

链式前向星

图的存储一般有两种：邻接矩阵、前向星。

邻接矩阵很方便，但是缺点也明显：

1.若图是稀疏图，边很少，开二维数组a[][]浪费;

2.若点很多(如10000个点)a[10000][10000]又会爆.只能用前向星做.

前向星的效率不是很高，优化后为链式前向星，直接介绍链式前向星。

（一）链式前向星

1. 结构

这里用两个东西：

1 结构体数组edge存边，edge[i]表示第i条边,

2 head[i]存以i为起点的第一条边(在edge中的下标)

struct node{

int next; //下一条边的存储下标

int to; //这条边的终点

int w; //权值

}edge[500010];

2.增边

若以点i为起点的边新增了一条，在edge中的下标为j.

那么edge[j].next=head[i];然后head[i]=j.

即每次新加的边作为第一条边，最后倒序遍历

void Add(int u, int v, int w) //起点u, 终点v, 权值w
tot为边的计数，从0开始计 
{
    edge[tot].v=v;
    edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot++;
}

3. 遍历

遍历以st为起点的边

memset(head,-1,sizeof(head));
for(int i=head[st]; i!=-1; i=edge[i].next)

举个例子：

i开始为第一条边，每次指向下一条(以-1为结束标志)  （若下标从1开始，next应初始化0）

存在边1,3   1,4   2,5   2,6   4,3   5,3  六条边

依次调用函数add_edge之后，可以得到

edge[0].to=3; edge[0].next=-1; head[1]=0;

edge[1].to=4; edge[1].next=0; head[1]=1;

edge[2].to=5; edge[2].next=-1; head[2]=2;

edge[3].to=6; edge[3].next=2; head[2]=3;

edge[4].to=3; edge[4].next=-1; head[4]=4;

edge[5].to=3; edge[5].next=-1; head[5]=5;