[模板]数组模拟邻接表模板+理解

发布于 2019-07-22  607 次阅读


{
    int u;//保存每一条边的起始点
    int v;//保存每一条边的终止点
    int w;//保存每一条边的权值
    int next;//保存每一条边的上一条边的编号
}edge[maxn*2];//保存每一条边,下标表示每一条边的编号
int head[maxn];//保存每一个顶点的起始边的编号(最后一个连接到这个点的边)

有向图建图

void add(int u,int v,int w,int &k)
{
    edge[k].u=u;
    edge[k].v=v;
    edge[k].w=w;
    edge[k].next=head[u];//这条边的上一条边的编号
    head[u]=k++;//这个顶点的起始边的编号等于当前边标号+1
}

无向图建图

void add(int u,int v,int w,int &k)
{
    edge[k].u=u;
    edge[k].v=v;
    edge[k].w=w;
    edge[k].next=head[u];
    head[u]=k++;
    swap(u,v);
    edge[k].u=u;
    edge[k].v=v;
    edge[k].w=w;
    edge[k].next=head[u];
    head[u]=k++;
}

遍历每个点所连接的边

for(int k=head[u];k!=-1;k=edge[k].next)//k=u的起始边 
{
    int v=edge[k].v;
    int w=edge[k].w;
    cout<<"起点:"<<u<<endl;
    cout<<"终点:"<<v<<endl;
    cout<<"权值:"<<w<<endl;
}

愿风指引你的道路,愿你的刀刃永远锋利。