邻接表的建图

小灰灰 2022-10-01 04:47 141阅读 0赞

typedef struct
    {
        int to;
        int w;
        int next;
    }Edge;
    Edge e[MAX];
    int pre[MAX];
    
    //初始化
    memset(pre,-1,sizeof(pre));
    
    //输入
    scanf("%d %d %d",&from,&to,&w1);
    e[i].to = to; e[i].w = w1; e[i].next = pre[from]; pre[from] = i;
    i++;

上面这段代码中，边的结构体Edge由三个元素组成：弧头结点序号，边权值，下一条边的序号。e\[i\]指的是第i条边。pre\[i\]记录的是从当前输入的情况来看，序号为i的弧尾结点发出的第一条边的序号是pre\[i\]。

这样，在操作某个结点发出的边时，可以像这么做：

/*now为弧尾结点序号，i为now所发出的边序号，adj为弧头结点序号，w为now-->adj这条边的权值*/
    for(i = pre[now]; i != -1; i = edge[i].next)
    {
         int adj = edge[i].to;
         int w = edge[i].w;
         //do something...
    }

下面给出一份具体的有向图邻接表模板代码

*/
    /*
    *  构建邻接表模板
    *
    */
    #include<stdio.h>
    #include<string.h>
    int head[100100];//表头，head[i]代表起点是i的边的编号
    int cnt;//代表边的编号
    struct s
    {
        int u;//记录边的起点
        int v;//记录边的终点
        int w;//记录边的权值
        int next;//指向上一条边的编号
    }edge[100010];
    void add(int u,int v,int w)//向所要连接的表中加入边
    {
        edge[cnt].u=u;
        edge[cnt].v=v;
        edge[cnt].w=w;
        edge[cnt].next=head[u];
        head[u]=cnt++;
    }
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            int i;
            cnt=0;
            memset(head,-1,sizeof(head));//清空表头数组
            for(i=0;i<n;i++)
            {
                int u,v,w;
                scanf("%d%d%d",&u,&v,&w);
                add(u,v,w);//加上add(v,u,w);这句就是无向图邻接表了
            }
            int u,v,w;
            scanf("%d",&u);
            for(i=head[u];i!=-1;i=edge[i].next)//输出所有与起点为u相连的边的终点和权值
            {
                 v=edge[i].v;
                 w=edge[i].w;
                 printf("%d %d\n",v,w);
            }
        }
        return 0;
    }