链式前向星

链式前向星

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

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

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）