2023·41 有向图 K 顶点：数一遍出入度就完了

本文属于「从暴力解到最优解」专题的第二组。这道题没有暴力解到最优解的落差——扫一遍矩阵统计出入度，直接就是标准答案。分不在优化，在把行列方向和边界条件写准。

题目

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

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

将图中出度大于入度的顶点称为 K 顶点。设计算法 int printVertices(MGraph G)：对给定任意非空有向图 G，输出 G 中所有 K 顶点，并返回 K 顶点的个数。要求：(1) 给出算法的设计思想；(2) 根据算法思想，写出 C/C++ 描述，并注释。总分 10 分。

先看一眼题面：没有出现「尽可能高效」。按总纲的分类，这道题属于第二组——没有额外的最优性要求悬在头顶。但没有最优性要求，不代表随便写就能拿满分，下面会看到分数具体卡在哪。

直观解法：扫一遍矩阵统计出入度

题目已经把判定条件摆在眼前：出度大于入度的顶点就是 K 顶点。邻接矩阵下，Edge[i][j] != 0 表示存在弧 $i \to j$ ，这条弧同时贡献：顶点 $i$ 的出度加 1，顶点 $j$ 的入度加 1。于是一次双重扫描就能同时统计出所有顶点的出度和入度：

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^{2})$ ；两个度数组，空间 $O (n)$ 。

为什么它就是满分解

用总纲的「找浪费三问」审一遍：

有没有重复扫描？ 没有。每个矩阵元素只读一次，同时更新对应的出度和入度。
有没有重算已知的东西？ 没有。每条弧对出入度的贡献只算一次，存进数组备用。
有没有放着性质不用？ 没有。题目没给任何额外结构（比如有序、稀疏），邻接矩阵本身就是稠密表示。

更根本的一条：图用邻接矩阵存储，要判断每个顶点的出入度，就必须把这 $n^{2}$ 个矩阵元素完整读一遍——这是该存储方式下的理论下界，不存在跳过某些元素还能保证正确的写法。既然已经碰到下界，直观写法就是最优解。

真正的难点在这里

这道题的分数不看谁写得快，看三个细节有没有踩对。

难点一：行列方向别搞反。 邻接矩阵下，第 $i$ 行非 0 项个数是顶点 $i$ 的出度（ $i$ 指向别人），第 $i$ 列非 0 项个数是顶点 $i$ 的入度（别人指向 $i$ ）。一次扫描写法里体现为 Edge[i][j] != 0 时 outDeg[i]++（i 是弧的起点）、inDeg[j]++（j 是弧的终点）。一旦把这两行反过来写——变成 outDeg[j]++、inDeg[i]++——所有顶点的出入度全部对调，K 顶点判定盘全错，而且这种错误在小规模测试里也不容易一眼看出来（因为代码依然能跑、依然会输出点什么）。

难点二：outDeg 必须严格大于 inDeg。 题面定义是「出度大于入度」，代码里对应 outDeg[i] > inDeg[i]，不是 >=。用题面给的例子验证：顶点 c 出度 1、入度 1，出度不大于入度，c 不是 K 顶点；如果误写成 >=，c 会被错误地算进去，K 顶点集合就从 {a, b} 变成 {a, b, c}，和题面示例直接矛盾。

难点三：输出的是顶点名，不是下标。 题目要求「输出 G 中所有 K 顶点」，顶点的标识是 VerticesList[i] 里存的字符，不是数组下标 i 本身。printf("%c ", G.VerticesList[i]) 才对；写成 printf("%d ", i) 虽然也能跑，但答非所问。

这三条里，方向反是最隐蔽的错误——因为代码结构完全正确，只是两行顺序或者两个数组的角色互换了，考场上不容易自查出来，最好的办法是用题面给的例子亲手代入验证一遍。

扫矩阵统计出入度，看一遍

用题面例子搭一个 4 顶点有向图：a→b、a→d、b→d、b→c、c→d。演示逐元素扫描、同时累加出度和入度，最终数出 K 顶点 {a, b}，count = 2：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

别画蛇添足

别用邻接表思路来解这道题。 邻接矩阵下求入度天然要扫一整列（或整个矩阵），如果脑子里想着邻接表「出度容易入度难」的经验，硬要额外建一份反向邻接表来求入度，只会让代码变长、出错点变多——本题给定的就是邻接矩阵，直接扫它才是最短路径。
别真的去建图、做遍历。 这道题只问「出度和入度谁大」，是纯粹的计数问题，不需要 DFS/BFS，不需要访问标记数组，也不需要建任何辅助图结构。看到「有向图」就条件反射地想遍历，是这类题最容易多花冤枉时间的地方。

下一步

在 OJ 上验证你的写法：ds-2023-41 有向图 K 顶点
回到题库看这道题的完整解析与错因：真题库 · 数据结构

2023·41 有向图 K 顶点：数一遍出入度就完了 ​

题目 ​

直观解法：扫一遍矩阵统计出入度 ​

为什么它就是满分解 ​

真正的难点在这里 ​

扫矩阵统计出入度，看一遍 ​

别画蛇添足 ​

下一步 ​