首页 > 代码库 > 邻接表

邻接表

除了邻接矩阵外储存图的另一种方法,适用于稀疏图。

用一个有n结点,p条边的有向图,用a[i],b[i],l[i]分别表示第i条边的起点,终点,权值。first[x]表示x号结点连出的第一条边,next[i]表示与第i条边是同一个结点连出的下一条边,如果为0则表示已经没有下一条了

初始化:用last[x]表示第x号结点目前已读入的最后一条边,方便操作

void init()
{
    for (int i=1;i<=p;cin>>a[i]>>b[i]>>l[i],i++)
        if (last[a[i]]==0)
            first[a[i]]=last[a[i]]=i;
        else
            last[a[i]]=next[last[a[i]]]=i;
}

调用:对于第x号结点,调用它连出的每一条边和每一个点

void print(int x)
{
    int u=first[x];
    while (u!=0)
    {
        cout<<b[u]<<endl;//输出终点
        cout<<l[h]<<endl;//输出权值
        u=next[u];//前往下一条边
    }
}