C语言图的邻接表存储

短命女 2022-02-15 16:57 215阅读 0赞

1.邻接表法

邻接表有两个部分：顶点节点、边节点

（1）顶点节点

建立一个顺序表，用来存储图中所有顶点。每个顶点为表中一个元素，每个元素包含：数据域和指针域（firstedge）

数据域：存储节点信息，如节点名称

指针域：指向顶点的第一个邻接点

存储结构如下：

#define MAX_VERTEX_NUM 100 // 图中最大节点数
    typedef struct vnode       // 顶点结构
    {
        VertexType vex;      // 存储顶点名
        EdgeNode *firstedge; // 边表头指针，指向顶点第一个邻接点
    } VertexNode, AdjList[MAX_VERTEX_NUM];

（2）边节点

为顺序表中每个顶点建立一个单链表，单链表中每个节点都是顶点的临界点。每个边节点包含：数据域和指针域（next）

数据域：存储节点信息，如节点名称

指针域：指向顶点的下一个邻接点

有时还会增加一个域，用来存储边上的信息，如权值（此项不需要时可以不加）

存储结构如下：

typedef char VertexType;
    typedef struct node // 边表节点
    {
        VertexType adjvex; // 与顶点相连的邻接点下标(adjoin：邻接)
        struct node *next; // 指向顶点的下一个邻接点
    } EdgeNode;

（3）图示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70][]

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_VERTEX_NUM 100 // 图中最大节点数
    typedef char VertexType;
    typedef struct node // 边表节点
    {
        VertexType adjvex; // 与顶点相连的邻接点下标(adjoin：邻接)
        struct node *next; // 指向顶点的下一个邻接点
    } EdgeNode;
    
    typedef struct vnode // 顶点结构
    {
        VertexType vex;      // 存储顶点名
        EdgeNode *firstedge; // 边表头指针，指向顶点第一个邻接点
    } VertexNode, AdjList[MAX_VERTEX_NUM];
    
    typedef struct {
        AdjList adjlist; // 描述图结构的邻接表
        int vexnum;      // 节点的数目
        int edgenum;     // 边的数目
    } ALGraph;           // adjacency list：邻接表
    
    void LocateVex(ALGraph ALG,
                   VertexType vertex); // 若图ALG中存在节点vertex，则返回该节点下标
    void CreateALG(ALGraph *ALG);  // 邻接表法创建图
    void TraverseALG(ALGraph ALG); // 遍历图ALG
    
    int main(void)
    {
        ALGraph g;
    
        CreateALG(&g);
        printf("------------------------------\n");
        printf("vexnum = %d ; edgenum = %d\n", g.vexnum, g.edgenum);
        printf("------------------------------\n");
        LocateVex(g, '0');
        printf("------------------------------\n");
        TraverseALG(g);
    
        return 0;
    }
    void CreateALG(ALGraph *ALG)
    {
        VertexType ch;
        int i = 0, count = 0;
        EdgeNode *temp;
    
        printf("请输入图的顶点：");
        // 建立顶点表
        while ((ch = getchar()) != '\n') {
            ALG->adjlist[i].vex = ch;
            ALG->adjlist[i].firstedge = NULL;
            i++;
        }
        ALG->vexnum = i; // 顶点数
    
        // 头插法建立顶点的邻接边表
        for (i = 0; i < ALG->vexnum; i++) {
            printf("请输入顶点 %c 的邻接顶点：", ALG->adjlist[i].vex);
            // 按下回车结束邻接点的创建
            while ((ch = getchar()) != '\n') {
                temp = (EdgeNode *)malloc(sizeof(EdgeNode));
                temp->adjvex = ch;
                temp->next = ALG->adjlist[i].firstedge;
                ALG->adjlist[i].firstedge = temp;
                count++;
            }
        }
        ALG->edgenum = count / 2;
        // 无向图中每条边连接两个顶点，故：节点总度数 = 边数 * 2
    }
    void TraverseALG(ALGraph ALG)
    {
        int i;
        EdgeNode *temp;
    
        if (ALG.vexnum == 0) {
            printf("图为空\n");
            return;
        }
    
        // 遍历图
        for (i = 0; i < ALG.vexnum; i++) {
            printf("顶点 %c ：", ALG.adjlist[i].vex);
            temp = ALG.adjlist[i].firstedge;
            // 输出图的信息
            while (temp) {
                printf("[ %c ] -> ", temp->adjvex);
                temp = temp->next;
            }
            printf("NULL\n");
    
            // 以另一种方式输出图的信息
            /*
             * while (temp) {
             *     printf("(%c, %c) ", ALG.adjlist[i].vex, temp->adjvex);
             *     temp = temp->next;
             * }
             * printf("\n");
             */
        }
    }
    
    void LocateVex(ALGraph ALG, VertexType vertex)
    {
        int i;
    
        for (i = 0; i < ALG.vexnum; i++) {
            if (ALG.adjlist[i].vex == vertex) {
                printf("节点下标：%d\n", i);
                return;
            }
        }
        printf("该节点不存在！\n");
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220215/43f4eab7c88543c997fdae0a0974bf97.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]: /images/20220215/a0dd2da4c5a348ce9320534fbbe4d701.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2]: /images/20220215/58af81c0ef3544c69015ed885817d8a1.png