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

小咪咪 2022-06-17 04:09 227阅读 0赞

所谓“邻接矩阵”的存储方式就是用一个一维数组存储图中全部的n个顶点的信息，用一个n×n的矩阵表示图中各顶点的邻接关系和权值。在矩阵中用1或0表示顶点间是否存在邻接关系。如果是网图的话，用0或∞表示不邻接（0可能被用作权值），用一个非零数表示权值。  
根据图和矩阵的性质，该存储方式应具有以下特点：

1.  无向图的邻接矩阵一定是一个对称阵，所以在存储时只需存储矩阵的上三角即可。
2.  由于这里讨论的是简单图，所以图中不存在自回路，所以矩阵的主对角线元素都为0。
3.  对于无向图，矩阵第i行（或第i列）的非零元素个数正好是第i个顶点的度。
4.  对于有向图，矩阵第i行（或第i列）的非零元素个数正好是第i个顶点的出度（或入度）。

下面给出邻接矩阵存储图的代码描述。

以下是存储结构的声明。

#define MaxVertexNum 100    //最大顶点数设为100
    #define INFINITY 65535      //无穷设为双字节无符号整数的最大值65535
    
    enum GraphType {DG, UG, DN, UN}; //有向图，无向图，有向网图，无向网图
    typedef stuct Mgraph{
        char Vertices[MaxVertexNum];          //顶点表
        int Edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，即边表
        int n,e;                                    //顶点数n，边数e
        enum GraphType GType;                       //图的类型分为四种：DG，UG，DN，UN
    }* MGraph;              //MGraph是以邻接矩阵存储的图类型

下面以无向图为例给出初始化算法。

MGraph CreateMGraph()
    {
        MGraph G;
        int w;
        G = (MGraph)malloc(sizeof(struct Mgaph));
        G->Gtype = UN;
        printf("输入定点数和边数（格式：顶点数，边数）：\n");
        scanf("%d,%d",&(G->n),&(G->e));
        printf("输入顶点信息（用空格隔开）：\n");
        for(int i = 0; i < G->n; i++){
            scanf("%c",&G->Vertices[i]);
            getchar();
        }
        for(int i = 0; i < G->n; i++)
            for(int j = 0; j < G->n; j++)
                G->Edges[i][j] = INFINITY; //初始化邻接矩阵
        printf("输入每条边对应的两个顶点的序号和权值（格式：i，j，w）：\n");
        for(int i, j, k = 0; k < G->e; k++){
            scanf("%d,%d,%d", &i,&j,&w);
            G->Edges[i][j] = w;
            G->Edges[j][i] = w;
        }
        return G;
    }