A. DS图—图的邻接矩阵存储及度计算

邻接矩阵是图的一种常用表示方法，其基本思想是用一个矩阵来表示图中各个顶点之间的连接关系。具体来说，矩阵的行和列分别对应图中的顶点，矩阵中的元素表示相应顶点之间是否有边连接。对于无向图，邻接矩阵是一个对称矩阵，因为边的连接是双向的；对于有向图，邻接矩阵则不一定是对称的。

邻接矩阵的存储方式可以采用一维数组或二维数组，一维数组更节省空间，但访问元素时需要进行下标的计算，二维数组则更直观易懂，但占用空间较大。

邻接矩阵存储方式的优点是方便进行图的遍历、搜索和计算图的度等操作。其中，度是指与某个顶点相连的边的数量，对于无向图，每个顶点的度就是其相邻顶点的数量；对于有向图，每个顶点有出度和入度两个概念，分别表示以该顶点为起点和终点的边的数量。

计算图的度可以通过遍历邻接矩阵来实现。对于无向图，每个顶点的度可以通过遍历邻接矩阵中相应行的元素来计算；对于有向图，每个顶点的出度可以通过遍历邻接矩阵中相应行的元素来计算，入度则可以通过遍历邻接矩阵中相应列的元素来计算。

相关问题

6-2 求采用邻接矩阵作为存储结构的无向图各顶点的度 分数 6 作者 DS课程组 单位 临沂大学 本题要求实现一个函数，输出无向图每个顶点的数据元素的值，以及每个顶点度的值。 函数接口定义： void degree(MGraph G); G为采用邻接矩阵作为存储结构的无向图。 裁判测试程序样例： #include <stdio.h> #define MVNum 100 //最大顶点数 typedef struct{ char vexs[MVNum]; //存放顶点的一维数组 int arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和边数 }MGraph; void degree(MGraph G); void CreatMGraph(MGraph *G);/* 创建图 */ int main() { MGraph G; CreatMGraph(&G); degree(G); return 0; } void CreatMGraph(MGraph *G) { int i,j,k; scanf("%d%d",&G->vexnum,&G->arcnum); getchar(); for(i=0;i<G->vexnum;i++) scanf("%c",&G->vexs[i]); for(i=0;i<G->vexnum;i++) for(j=0;j<G->vexnum;j++) G->arcs[i][j]=0; for(k=0;k<G->arcnum;k++) { scanf("%d%d",&i,&j); G->arcs[i][j]=1; G->arcs[j][i]=1; } } /* 请在这里填写答案 */ 输入样例： 例如无向图 无向图.png 第一行给出图的顶点数n和边数e。第二行给出n个字符，表示n个顶点的数据元素的值。后面是e行，给出每一条边的两个顶点编号。 4 5 ABCD 0 1 0 2 1 2 1 3 2 3 输出样例： 输出n个顶点的元素值，顶点的数据类型为字符型。以及各顶点的度值 A:2 B:3 C:3 D:2

这道题要求实现一个函数，输出无向图每个顶点的数据元素的值，以及每个顶点度的值。我们可以通过遍历邻接矩阵来计算每个顶点的度，然后输出即可。

具体实现可以参考以下代码：

void degree(MGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        int degree = 0;
        for (int j = 0; j < G.vexnum; j++) {
            if (G.arcs[i][j] == 1) {
                degree++;
            }
        }
        printf("%c:%d ", G.vexs[i], degree);
    }
}

首先，我们在外层循环中遍历每个顶点，对于每个顶点，我们定义一个变量 `degree` 存储其度数，然后在内层循环中遍历其它顶点，如果邻接矩阵中该顶点与其它顶点之间存在边，则将 `degree` 值加 1。最后，输出该顶点的数据元素的值和其度数即可。

完整代码如下：