首页 > 代码库 > 邻接表

邻接表

2024-07-04 20:37:11   234人阅读

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

用一个有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];//前往下一条边
    }
}

 


联系
我们