【数据结构】图的存储结构：邻接表

深碍√TFBOYSˉ_ 2022-01-16 22:53 433阅读 0赞

## 图的存储结构 ##

由于图的任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即**图没有顺序存储结构**，但我们可以用二维数组（矩阵）来表示元素之间的关系——**邻接矩阵**。除此之外还有链式存储结构，包括**邻接表、十字链表和邻接多重表**。**其中邻接矩阵和邻接表最常用。**

## 邻接表 ##

邻接表（Adjacency List）是图的一种链式结构。图中有多少个顶点，就有多少个**单链表**，每个顶点分别作为每个单链表的**头结点**，与顶点相连的其余顶点**无序地（无特殊的顺序要求）**连接在对应的单链表上。

顶点间的关系蕴含在若干个单链表中，因此**邻接表图（ALGraph）**的结构体只需要包含\{每个单链表的头结点（即每个顶点）以及顶点数和边数\}。

为了方便管理头结点，我们可以把它们放到**一维数组ALs\[MaxVNum\]**中，且该一维数组的功能包含着**邻接矩阵图**中**vexs\[MaxVNum\]**的功能。

\*下面将头结点代表的顶点称作**起始顶点**。

再把注意力放到单链表上，由于起始顶点已经确定，所以与起始顶点相连的每一个顶点都分别对应着一条边，因此我们可以把单链表上的其余结点看作**边结点**。

**边结点**需要包含的信息有\{边依附的另一个顶点编号（因为顶点放在**一维数组ALs\[MaxVNum\]**中，所以顶点v1的编号为0，如此类推）、指向下一个边结点的指针以及边上的权\}。

**头结点**需要包含的信息有\{起始顶点的信息、指向下一个边结点的指针\}

依据上面的思路，我们一共需要创建**三个结构体**。

/*邻接表的结构表示*/
    
    typedef struct ArcNode         /*边结点*/
    {
        int anothervex;            /*另一个顶点的编号*/
        ArcNode *nextarcnode;      /*指向下一边结点的指针*/
        int weight;                /*权*/
    };
    
    typedef struct VexNode         /*头结点*/
    {
        VexType data;              /*起始顶点的信息*/
        ArcNode *nextarcnode;      /*指向下一边结点的指针*/
    };
    
    typedef struct ALGraph         /*邻接表图*/
    {
        VexNode ALs[MaxInt];       /*头结点数组*/
        int vexnum, arcnum;        /*顶点数、边数*/
    };

写出邻接表图的结构形式后，可以开始往里面放东西了。

下面以“**无向图**”为例写一下邻接表表示法的使用方法：

**<思路>**

**（1）**输入无向图的顶点数和边数；

**（2）**在**一维数组ALs\[MaxVNum\]**中输入起始顶点的信息，并使指针域初始化为**NULL**，**完成各单链表的初始化**；

**（3）**构造邻接表。输入**起始顶点va**和**相邻顶点va**的值，以及**(va,vb)的权w**。

**（4）new**一个**临时边结点tempnode**，使**tempnode**中“另一顶点的编号”为**vb的编号**，并使其指针指向**头结点指针**原本指向的“空间”，再令**头结点指针**指向**tempnode**，**完成tempnode的插入，即完成相邻顶点的连接**。

**（5）**因为这个是**无向图**，所以我们需要**对称地完成起始顶点为vb的单链表的插入**。

**（6）**在达到**边数arcnum**前**循环**执行步骤(3)(4)(5)。

int CreatUDG(ALGraph &G)
    {                                /*下面的代码已经按照<思路>步骤分块喽*/
        cin>>G.vexnum>>G.arcnum;
    
        int i, j;    
        for(i =0; i < G.vexnum; i++)
        {
            cin>>G.ALs[i].data;
            G.ALs[i].nextarcnode = NULL;
        }
    
        for(int k = 0; k < G.arcnum; k++)
        {
            cin>>va>>vb>>w;
            i = LocateVex(G, va); j = LocateVex(G, vb);
    
            tempnode1 = new ArcNode;
            tempnode1->anothervex = j;
            tempnode1->nextarcnode = G.ALs[i].nextarcnode;
            G.ALs[i].nextarcnode = tempnode1;
    
            tempnode2 = new ArcNode;
            tempnode2->anothervex = i;
            tempnode2->nextarcnode = G.ALs[j].nextarcnode;
            G.ALs[j].nextarcnode = tempnode2;
        }
    
        return 0;
    }

**邻接表的优缺点：**

1）优点：

a. **便于增加和删除顶点。**

b. **便于统计边的数量，时间复杂度为O(n+e)。**

c. **空间效率高。**

2）缺点：

a. **不便于判断顶点间是否有联系。**

b. **不便于计算有向图各个顶点的入度，需要遍历其余所有起始顶点的单链表。**

（点击传送门学习更多相关知识：[https://blog.csdn.net/Ha1f\_Awake/article/details/84383923][https_blog.csdn.net_Ha1f_Awake_article_details_84383923]）

[https_blog.csdn.net_Ha1f_Awake_article_details_84383923]: https://blog.csdn.net/Ha1f_Awake/article/details/84383923