数据结构图的邻接矩阵

柔情只为你懂 2022-05-25 02:41 196阅读 0赞

图的邻接矩阵的存储方式是用两个数组来实现的，一个一维数组存储顶点信息，一个二维数组存储线（无向图）或弧（有向图）的信息。

设图G有n个顶点，则邻接矩阵是一个n × n的方阵，定义为：

![70][]

![70 1][]

无向图的邻接矩阵，两个顶点有边则为1，否则，为0；因为是无向图arc\[i\]\[j\] = arc\[j\]\[i\]，所以矩阵为对称矩阵，对角线为自己到自己的边，邻接矩阵中，行之和或者列之和都为各顶点度的总数。

设图G有是网图，有n个顶点，则邻接矩阵是一个n × n的方阵，定义为：

![70 2][]

![70 3][]

无向网图和无向图差不多，就是加了权值，两个顶点之间无边的话距离是∞。

如果是有向图，邻接矩阵就不是对称矩阵了。

下面是邻接矩阵的存储结构：

#define MAXVERTEX 100   //图的最大顶点数
    #define INFINITY 32767  //用有符号的int最大值表示无穷大
    typedef char vertextype;    //定义定点的存储信息为字符型
    typedef int arctype;    //定义边的权值为int型
    
    //图的邻接矩阵的存储结构
    typedef struct
    {
        vertextype vertex[MAXVERTEX];   //顶点表
        arctype arc[MAXVERTEX][MAXVERTEX];  //邻接矩阵
        int vertexnum;  //图的当前顶点数
        int arcnum; //图的当前边数
    }MGraph;

存储结构里面主要由四部分构成，

第一部分是一个一维数组存储的是顶点信息，

第二部分是邻接矩阵由二维数组组成，存储着各顶点彼此之间的关系，

第三部分和第四部分分别是当前图的顶点数和线数。

下面是具体的代码实现（注释的很详细了）：

#include <iostream>
    using namespace std;
    
    #define MAXVERTEX 100   //图的最大顶点数
    #define INFINITY 32767  //用有符号的int最大值表示无穷大
    typedef char vertextype;    //定义定点的存储信息为字符型
    typedef int arctype;    //定义边的权值为int型
    
    //图的邻接矩阵的存储结构
    typedef struct
    {
        vertextype vertex[MAXVERTEX];   //顶点表
        arctype arc[MAXVERTEX][MAXVERTEX];  //邻接矩阵
        int vertexnum;  //图的当前顶点数
        int arcnum; //图的当前边数
    }MGraph;
    
    //创建无向网
    void CreateMGraph(MGraph &G)
    {
        cin >> G.vertexnum; //输入顶点数目
        cin >> G.arcnum;    //输入边数
        for(int i = 0; i < G.vertexnum; i++)    //输入顶点信息
            cin >> G.vertex[i];
        for(int i = 0; i < G.vertexnum; i++)    //将所有边初始化为无穷大
            for(int j = 0; j < G.vertexnum; j++)
                G.arc[i][j] = INFINITY;
        for(int k = 0; k < G.arcnum; k++)
        {
            int i, j, w;
            cin >> i >> j;  //输入构成边的两个顶点
            cin >> w;   //输入边所对应的权值
            G.arc[i][j] = w;
            G.arc[j][i] = G.arc[i][j];  //无向图的邻接矩阵为对称矩阵
        }
    }
    
    //打印邻接矩阵
    void PrintfMGraph(MGraph G)
    {
        for(int i = 0; i < G.vertexnum; i++)
        {
            for(int j = 0; j < G.vertexnum; j++)
                cout << G.arc[i][j] << '\t';
            cout << endl;
        }
    }
    
    //主函数
    int main()
    {
        MGraph G;
        CreateMGraph(G);
        PrintfMGraph(G);
        return 0;
    }

邻接矩阵的时间复杂度为O（n + n^2 + e），其中n为顶点数，e为边数，去掉低阶和系数后，变为O（n^2）。

运行结果（根据上面第二个图输入的数据）：

![70 4][]

[70]: /images/20220525/cd83608c17fa487ab69ae34ffa1ad540.png
[70 1]: /images/20220525/42ab772df97348fd9dcefcf58b7cd7b5.png
[70 2]: /images/20220525/6916e2f5bcba4d72b5d865b9b548a23f.png
[70 3]: /images/20220525/be93517bf56f4ca5b0c8b7159c9f1ce2.png
[70 4]: /images/20220525/341e66e8b640475eb0b210db7a5ff594.png