题目

已知有向图 G 采用邻接矩阵存储，类型定义如下：

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

将图中出度大于入度的顶点称为 K 顶点。例如在题 41 图中，顶点 a 和 b 都是 K 顶点。

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

(1) 给出算法的设计思想。

(2) 根据算法思想，写出 C/C++ 描述，并注释。

解析

(1) 设计思想

答案：扫一遍邻接矩阵，同时统计每个顶点的出度数组 outDeg[] 和入度数组 inDeg[]；再扫一遍顶点表，输出所有 outDeg[i] > inDeg[i] 的顶点，并计数返回。

邻接矩阵 Edge[i][j] != 0 表示存在弧 ，对应：

• 顶点 的出度加 1（i 行某个非 0 项）
• 顶点 的入度加 1（j 列某个非 0 项）

所以一次双重 for 循环就能同时统计所有顶点的入出度。

示例验证：题面给的图中，a → b、a → d、b → d、b → c、c → d，逐个计数：

顶点	出度	入度	出 > 入？
a	2	0	✓ K
b	2	1	✓ K
c	1	1	✗
d	0	3	✗

K 顶点 = {a, b}，与题面一致。

(2) 代码实现

#define MAXV 100

typedef struct {
    int  numVertices, numEdges;
    char VerticesList[MAXV];
    int  Edge[MAXV][MAXV];
} MGraph;

int printVertices(MGraph G) {
    int n = G.numVertices;
    int outDeg[MAXV] = {0};
    int inDeg [MAXV] = {0};
    int count = 0;

    // ① 一次双重扫描，同时统计每个顶点的出度和入度
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (G.Edge[i][j] != 0) {
                outDeg[i]++;       // i 出 1 条边
                inDeg [j]++;       // j 入 1 条边
            }

    // ② 扫一遍顶点，输出所有 K 顶点
    for (int i = 0; i < n; i++)
        if (outDeg[i] > inDeg[i]) {
            printf("%c ", G.VerticesList[i]);
            count++;
        }

    return count;
}

关键点说明：

• 一次双重循环就够，不需要分别扫两次。第一次扫行得出度、第二次扫列得入度是低效写法；用一次循环 + 两个累加器同时记录更省事，复杂度同为 O(n²) 但常数减半。
• 输出"顶点"不是"下标"：返回值是 K 顶点个数，但题目要求"输出 G 中所有 K 顶点"，所以打印时用 G.VerticesList[i]（顶点名），不要直接打印下标 i。
• 复杂度：时间 O(n²)，主要在双重扫描（与邻接矩阵的存储规模相当，已是该存储下的下界）；空间 O(n)，两个度数组。
• 若改为邻接表存储：出度天然容易（一个顶点的邻接链表长度），但入度需要倒过来扫所有链表，复杂度变为 O(n + e)。本题给定邻接矩阵，O(n²) 反而是最自然写法。