无向图的邻接表表示法

谁践踏了优雅 2022-06-15 11:14 190阅读 0赞

/*无向图的邻接表表示法*/
    #include<stdio.h>
    #define vnum 10
    typedef struct arcnode
    {
        int adjvex;                         /*下一条边的顶点编号*/
        struct arcnode * nextarc;           /*指向下一条边的指针*/
    }ArcNode;
    typedef struct vexnode
    {
        int vertex;                         /*顶点编号*/
        ArcNode *firstarc;                  /*指向第一条边的指针*/
    }AdjList[vnum];
    typedef struct gp
    {
        AdjList adjlist;
        int vexnum,arcnum;                  /*顶点和边的个数*/
    }Graph;
    CreateAdjlist(Graph *g,int x,int y)     /*创建并初始化邻接表*/
    {
        int i;
        g->vexnum=x;
        g->arcnum=y;
        for(i=0;i<g->vexnum;i++)
        {
            g->adjlist[i].vertex=i;         /*初始化顶点信息*/
            g->adjlist[i].firstarc=NULL;    /*初始化i的第一个邻接点为NULL*/
        }
    }
    InsertEdge(Graph *g)                    /*插入边*/
    {
        ArcNode *p;
        int i,j,k;
        for(k=0;k<g->arcnum;k++)
        {
            printf("输入第%d条边:",k+1);
            scanf("%d %d",&i,&j);
            p=(ArcNode *)malloc(sizeof(ArcNode));/*生成j的表结点*/
            p->adjvex=j;
            p->nextarc=g->adjlist[i].firstarc;   /*将结点j链接到i的单链表中*/
            g->adjlist[i].firstarc=p;
            p=(ArcNode *)malloc(sizeof(ArcNode));/*生成i的表结点*/
            p->adjvex=i;
            p->nextarc=g->adjlist[j].firstarc;   /*将结点i链接到j的单链表中*/
            g->adjlist[j].firstarc=p;
        }
    }
    OutGraph(Graph *g)                      /*输出邻接表*/
    {
        int i;
        for(i=0;i<g->vexnum;i++)
        {
            printf("[%d]:",i);
            while(g->adjlist[i].firstarc!=0)
            {
                printf("%d ",g->adjlist[i].firstarc->adjvex);
                g->adjlist[i].firstarc=g->adjlist[i].firstarc->nextarc;
            }
            printf("\n");
        }
    }
    main()
    {
        Graph g;
        int x,y;
        printf("输入顶点和边的个数:\n");
        scanf("%d %d",&x,&y);
        CreateAdjlist(&g,x,y);
        InsertEdge(&g);
        OutGraph(&g);
    }