题8

题8

题目

【2023 统考真题】已知有向图 G 采用邻接矩阵存储,类型定义如下:

typedef struct { // 图的类型定义
    int numVertices, numEdges; // 图的顶点数和有向边数
    char VerticesList[MAXV]; // 顶点表,MAXV 为已定义常量
    int Edge[MAXV][MAXV]; // 邻接矩阵
} MGraph;

将图中出度大于入度的顶点称为 K 顶点。例如,在下图中,顶点 a 和 b 为 K 顶点。

请设计算法 int printVertices (MGraphG), 对给定的任意非空有向图 G, 输出 G 中所有的K顶点,并返回K顶点的个数。要求:

1. 给出算法的基本设计思想。
2. 根据设计思想, 采用 C 或 C++ 语言描述算法, 关键之处给出注释。

分析

我们在学拓扑排序的时候，用的一个算法就是找入度为0的顶点，把它们挨个删去，这里是找出度为0的，两者都是要处理有向图的度
如果有向图的邻接矩阵a[i][j]==1，表示有一个由i到j的边，这也就是入度，如果是a[j][i]==1，表示有一个由j到i的边，这就是出度。也就是说，我们如果先遍历行，就可以统计到入度，如果先遍历列，就可以统计到出度，我们再设置一个数组k[i][2]，其中k[i][0]是节点i的入度，k[i][1]是节点i的出度，这样就可以统计到所有节点的入度和出度了。

解

题41

int printVertices(MGraph G) {
    int k[MAXV][2] = {0}, i, j, count = 0;
    for (i = 0; i < G.numVertices; i++) {
        for (j = 0; j < G.numVertices; j++) { //内层循环表示先遍历谁
            k[i][0] += G.Edge[j][i]; // 统计入度，第i列的所有行，表示从j到i的边，入度
            k[i][1] += G.Edge[i][j]; // 统计出度，第i行的所有列，表示从i到j的边，出度
        }
    }
    for (i = 0; i < G.numVertices; i++) {
        if (k[i][1] > k[i][0]) {
            printf("%c ", G.VerticesList[i]);
            count++;
        }
    }
    return count;
}