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

╰+哭是因爲堅強的太久メ 2022-01-16 22:45 431阅读 0赞

## 图的存储结构 ##

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

## 邻接矩阵 ##

邻接矩阵（Adjacency Matrix）是表示顶点之间**相邻关系**的矩阵，存储在**二维数组**中。

1）在无向图中，若顶点v1与v2有联系，v1与v3没有联系，则在矩阵中，(1,2)和(2,1)的值为1，(1,3)和(3,1)的值为0，**对称矩阵**；

2）在无向网中，若边(v1,v2)的权为7，v1与y3没有联系，则在矩阵中，(1,2)和(2,1)的值为7，(1,3)和(3,1)的值为**∞（无限）**；

3）在有向图中，若v1为弧尾，v2为弧头，v2不指向v1，则在矩阵中，(1,2)的值为1，(2,1)的值为0；

4）有向网的情况可以类推。

\*需要注意的是，矩阵和二维数组的“坐标”含义是不同的，**矩阵的(1,1)等价于二维数组中的\[0,0\]**。

**邻接矩阵仅记录着任意两点间的联系，我们还需要一个一维数组来记录每个顶点的信息**，有边有顶点，这样才能构成一个完整的图。

清楚邻接矩阵的使用方法后，我们可以轻松写出以它为基础的图的结构形式。

为了避免概念的混淆，之后我会把图称作**邻接矩阵图（AMGraph）**。

/*邻接矩阵的结构表示*/
    
    #include <iostream>
    using namespace std;
    
    #define MaxInt 32767       /*表示∞（无限）*/
    #define MaxVNum 100        /*表示图中最多可以包含的顶点数*/
    
    typedef char Vextype;      /*将顶点的数据类型设为字符型，如果你喜欢也可以把它设成更复杂的结构体*/
    typedef int Arctype;       /*将边的权值设为整型*/
    
    typedef struct
    {
        Vextype vexs[MaxVNum];              /*用来保存顶点信息的一维数组*/
        Arctype arcs[MaxVNum][MaxVNum];     /*邻接矩阵*/
        int vexnum, arenum;                 /*记录图的顶点数和边数*/
    } AMGraph;                              /*将结构体命名为AMGraph*/

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

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

**<思路>**

**（1）**数一下无向网有多少个顶点（**vexnum**），多少条边（**arcnum**），然后将数值输入。当然，你也可以凭空造一个网，在先前定义的**MaxVNum**内赋值就行。

**（2）**在**一维数组vex**内输入顶点信息，一个循环完成。

**（3）**初始化邻接矩阵，将每个权值初始化为**MaxInt**。为什么呢？因为矩阵里除了若干个权值外，剩余的都是**MaxInt**，不可能先把权值填好，再来一个个把没有权值的地方填上**MaxInt**，这样效率极低而且繁琐。

**（4）**构造邻接矩阵。依次输入每条边依附的两个**顶点v1和v2**以及其**权值w**并赋值。因为输入的v1、v2有可能不在0~MaxInt的范围内，而且矩阵和二维数组的“坐标”含义是不同的，即**矩阵的(1,1)等价于二维数组中的\[0,0\]**，所以需要一个**函数LocateVex()**帮助判断、转化并确定“坐标”。

int CreatUDN(AMGraph &G)      /*UDN意为Omnidirectional Net，无向网*/
    {                             /*上面<思路>中写了的东西下面就不再啰嗦喽*/
        int i, j, w;
        cin>>G.vexnum>>G.arcnum;
        
        for(i = 0; i < G.vexnum; i++) cin>>G.vexs[i];
    
        for(i = 0; i < G.vexnum; i++)
            for(j = 0; j < G.vexnum; j++)
                G.arcs[i][j] = MaxInt;
    
        for(int k = 0; k < G.arcnum; k++)
        {
            cin>>v1>>v2>>w;
            i = LocateVex(G, v1); j = LocateVex(G, v2);
            G.arc[i][j] = G.arc[j][i] = w;
        }
     
        return 0;
    }

**邻接矩阵的优缺点：**

1）优点：

a. **便于判断两个顶点是否有联系。**确定顶点后再确定矩阵上的相应位置是否非0或非MaxInt即可。

b. **便于计算各个顶点的度。**其实也不用计算，数就完事了。对于**无向图**，多少个(1,n)的值为1，v1的**度**就是多少；对于**有向图**，多少个<1,n>的值为1，v1的**出度**就是多少，多少个<n,1>的值为1，v1的**入度**就是多少。

2）缺点：

a. **不便于增加和删除顶点。**非链式结构的通病。

b. **不便于统计边的数目**，需要遍历邻接矩阵的所有元素，**时间复杂度为O(n²)**。无向图遍历完后还要除以2。

c. **空间复杂度高。**非链式结构的另一通病，稀疏图（边或弧数较少）尤其浪费空间。

（点击传送门学习更多相关知识：[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