邻接矩阵

傷城~ 2022-04-23 01:02 186阅读 0赞

### 题目描叙： ###

无向图的表示方法邻接矩阵，需打印到屏幕。有权。

##### 分析：邻接矩阵的核心思想便是顶点表和边表。 #####

我们可以定义一个结构体，里面包含一个顶点表（即一个vexs一维数组），一个边表（即一个arc二维数组），还有两个整形变量(即一个表示为顶点数，另外一个表示为边数）。我们将二维数组初始化为无穷大（在此程序中用65535表示无穷大）。如果顶点i到顶点j有边（即此两个顶点是连接的），那个arc\[ i \]\[ j \]里面的值即顶点i与顶点j之间的权。因为，二维数组一开始初始化为无穷大。所以我们可以知道，如果二维数组里面的值不是无穷大的，则此值的下标i和下标j分别代表顶点i和顶点j。且i和j顶点是有边连接的。  
因为是无向图，所以顶点i能到顶点j就表示了顶点j能到顶点i。且他们之间的权是相同的。最后打印出来会发现，二维数组是关于主对角线对称的。 我在这个程序中将下标i和下标j相同的位置的值置位0（即权为0）。

#include"stdio.h"
    typedef char VertexType;  //顶点类型
    typedef int EdgeType;    //边的类型
    #define  MAXVEX 100   //最大顶点数
    #define INFINITY 65535 //表无穷。权的无穷大，即权不存在
    typedef struct
    {
        VertexType vexs[MAXVEX];    //顶点集
        EdgeType arc[MAXVEX][MAXVEX]; //边集
        int numVertexes,numEdges;//图中的顶点数和边数
    }MGraph;
    //建立一个无向网图的邻接矩阵表示
    void CreateMGraph(MGraph *G)
    {
        int i,j,k,w;
        char T;
        printf("请输入需建立图的顶点数和边数：\n");
        scanf("%d%d",&G->numVertexes,&G->numEdges);
        scanf("%c",&T);
        for(i=0;i<G->numVertexes;i++)
            scanf("%c",&G->vexs[i]);
        for(i=0;i<G->numVertexes;i++)
            for(j=0;j<G->numVertexes;j++)
                  {
                      G->arc[i][j]=INFINITY;
                      if(i==j)
                        G->arc[i][j]=0;
                  }
        for(k=0;k<G->numEdges;k++)
        {
            printf("输入边的下标i和下标j:\n");
            scanf("%d%d",&i,&j);
            printf("请输入边（vi，vj）上的权w的值:\n");
            scanf("%d",&w);
            G->arc[i][j]=w;
            G->arc[j][i]=w;//因为是无向图，矩阵对称
    
        }
    }
    int main()
    {
        MGraph G;
        int i,j;
        CreateMGraph(&G);
        //打印二维数组，可观察到此图的信息
        for(i=0;i<G.numVertexes;i++)
        {
            for(j=0;j<G.numVertexes;j++)
                printf("%7d ",G.arc[i][j]);
            printf("\n");
        }
    }