数据结构——图的邻接表、图的存储结构

╰+攻爆jí腚メ 2023-06-22 13:49 1阅读 0赞

要理解基础的话可以下看下b站这位老师的视频

数据结构与算法基础--第10周05--6.4图的存储结构5-6.4.2邻接表表示法1-无向图的邻接表

下面是一个无向的网图：

![70][]

邻接表中数据的存储图示如下

![70 1][]

顶点表也就是个结构体数组，是存放顶点的结构，顶点表中有data元素，存放顶点信息  firstarc是一个边结构体表指针，存放邻接点的信息。

边表也是一个结构体，内有adivex元素，存放邻接点的下标，weight存放顶点与邻接点之间线的权重，next是边表结构体指针，存放该顶点的下一个邻接点，next就是负责将顶点的邻接点连起来。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5OTgzMDY_size_16_color_FFFFFF_t_70][]

来做个例题：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5OTgzMDY_size_16_color_FFFFFF_t_70 1][]

按照头结点数组下标从1开始，表结点按邻接顶点编号降序创建邻接表

答案：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5OTgzMDY_size_16_color_FFFFFF_t_70 2][]

有向图就不说太详细了，感觉那个还简单些！

代码也贴一下吧

#include <iostream>
    using namespace std;
     
    #define MAXVERTEX 100   //最大顶点数
    typedef char vertextype;    //定义顶点的存储类型
    typedef int arctype;    //定义边的权值类型
     
    typedef struct ArcNode  //边表节点
    {
        int adjvex; //邻接点域，存储该顶点对应的下标
        arctype wigth;  //用于存储权值
        struct ArcNode *next; //链域，指向下一个邻接点
    }ArcNode;
     
    typedef struct VertexNode   //顶点表节点
    {
        vertextype data;    //存储顶点数据的信息
        ArcNode *firstarc;  //边表头指针
    }VertexNode, AdjList[MAXVERTEX];
     
    typedef struct
    {
        AdjList adjlist;    //定义邻接表
        int numvertex;  //当前邻接表的顶点数
        int numarc; //当前邻接表的边数
    }GraphAdjList;
     
    //建立图的邻接表
    void CreateAdjListGraph(GraphAdjList &G)
    {
        ArcNode *e;
        cin >> G.numvertex; //输入当前图的顶点数
        cin >> G.numarc;    //输入当前图的边数
        for(int i = 0; i < G.numvertex; i++)    //建立顶点表
        {
            cin >> G.adjlist[i].data;   //输入顶点信息
            G.adjlist[i].firstarc = NULL;   //将表边指针置为空
        }
        for(int k = 0; k < G.numarc; k++)
        {
            int i, j, w;
            cin >> i >> j >> w; //输入边两边的顶点和边上的权重
            e = new ArcNode;   //创建一个表边节点指针
            e->adjvex = j;
            e->wigth = w;
            e->next = G.adjlist[i].firstarc;
            G.adjlist[i].firstarc = e;
            //因为是无向图，彼此相对称
            e = new ArcNode;   //创建一个表边节点指针
            e->adjvex = i;
            e->wigth = w;
            e->next = G.adjlist[j].firstarc;
            G.adjlist[j].firstarc = e;
        }
    }
     
    //打印邻接表
    void PrintfGraphAdjList(GraphAdjList G)
    {
        for(int i = 0; i < G.numvertex; i++)
        {
            ArcNode *p = G.adjlist[i].firstarc;
            cout << G.adjlist[i].data << '\t';
            while(p)
            {
                cout << p->adjvex << ' ' << p->wigth << '\t';
                p = p->next;
            }
            cout << endl;
        }
    }
    int main()
    {
        GraphAdjList G;
        CreateAdjListGraph(G);
        PrintfGraphAdjList(G);
        return 0;
    }

[70]: https://img-blog.csdn.net/20180508185647682?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MDQzMTAw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: https://img-blog.csdn.net/20180508193352978?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MDQzMTAw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5OTgzMDY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191216165023877.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5OTgzMDY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5OTgzMDY_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191216165215278.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5OTgzMDY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5OTgzMDY_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191216165250139.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5OTgzMDY=,size_16,color_FFFFFF,t_70