邻接表

ゝ一纸荒年。 2022-04-23 01:08 159阅读 0赞

### 题目描叙： ###

使用邻接表保存无向图的信息。需要保持权。

##### 分析：邻接表的基本思想是数组与链表之间的结合。 #####

邻接矩阵的话，可以明确的表示出来哪个顶点和哪个顶点时相连接的。并且他们之间的权也是可以直接观察得到。  
邻接表的思想大致是：将当前结点相邻接的结点使用链表将邻接的结点的相关信息链接到当前结点后面。  
由于是无向图，所以结点i如果与结点j相连接。则即结点j与结点i相连接。

#include"stdio.h"
    #include"string.h"
    #define MAXVEX 10000
    typedef char VertexType; //顶点类型由用户自定义
    typedef int EdgeType;   //边的类型由用户自定义
    typedef struct EdgeNode //边表结点
    {
        int adjvex; //邻接点域，存储该结点对应的下标
        EdgeType weight; //存储权值
        struct EdgeNode *next; //链域，指向下一个邻接点
    }EdgeNode;
    typedef struct VertexNode //顶点表结点
    {
        VertexType data;
        EdgeNode *firstedge;
    }VertexNode,AdjList[MAXVEX];
    typedef struct
    {
        AdjList adjList;
        int numVertexes,numEdges;//图中的顶点数和边数
    }GraphAdjList;
    //建立图的邻接表结构  无向图
    void CreateALGraph(GraphAdjList *G)
    {
        int i,j,k,w;
        EdgeNode *e;
        char T;
        printf("请输入顶点数和边数:\n");
        scanf("%d%d",&G->numVertexes,&G->numEdges);
        scanf("%c",&T);
        for(i=0;i<G->numVertexes;i++)
        {
            scanf("%c",&G->adjList[i].data);//输入顶点信息
            G->adjList[i].firstedge=NULL;//将边表置为空表
        }
        for(k=0;k<G->numEdges;k++)
        {
            printf("请输入边（vi，vj）上的顶点序号及权值:\n");
            scanf("%d%d%d",&i,&j,&w);
            e=(EdgeNode *)malloc(sizeof(EdgeNode));//向内存申请空间 生成边表结点
            e->adjvex=j;//邻接序号为j
            e->weight=w;
            e->next=G->adjList[i].firstedge;//将e指针指向当前顶点指向的结点
            G->adjList[i].firstedge=e;//将当前结点的指针指向e
            //因为是无向图
            e=(EdgeNode *)malloc(sizeof(EdgeNode));//向内存申请空间 生成边表结点
            e->adjvex=i;//邻接序号为i
            e->weight=w;
            e->next=G->adjList[j].firstedge;//将e指针指向当前顶点指向的结点
            G->adjList[j].firstedge=e;//将当前结点的指针指向e
    
        }
    
    }
    int main()
    {
        GraphAdjList G;
        int i,j;
        CreateALGraph(&G);
        for(i=0;i<G.numVertexes;i++)
        {
            printf("\n%c:\n",G.adjList[i].data);
            while(G.adjList[i].firstedge!=NULL)
            {
                printf("%d:%d->",G.adjList[i].firstedge->adjvex,G.adjList[i].firstedge->weight);
                G.adjList[i].firstedge=G.adjList[i].firstedge->next;
            }
    
        }
    }