2023 年第 41 题

题目描述

已知有向图 G 采用邻接矩阵存储。将图中出度大于入度的顶点称为 K 顶点。请设计算法输出图中所有 K 顶点，并返回 K 顶点的个数。

解题思路

对于邻接矩阵：

• 第 i 行元素之和就是顶点 i 的出度。
• 第 i 列元素之和就是顶点 i 的入度。

所以只要对每个顶点各统计一次入度和出度：

1. 扫描第 i 行，求出度。
2. 扫描第 i 列，求入度。
3. 若 outdegree > indegree，则输出该顶点并计数。

手算示例

设邻接矩阵对应顶点 a, b, c, d，统计结果如下：

a: out = 2, in = 1  -> K 顶点
b: out = 3, in = 1  -> K 顶点
c: out = 1, in = 2  -> 不是
d: out = 1, in = 3  -> 不是

输出：

a b
个数 = 2

Python 实现

def print_k_vertices(vertices, edge):
    """
    vertices: 顶点名称列表
    edge: 邻接矩阵，edge[i][j] 为 1 表示 i -> j
    """
    n = len(vertices)
    result = []

    for v in range(n):
        outdegree = sum(edge[v][i] for i in range(n))
        indegree = sum(edge[i][v] for i in range(n))
        if outdegree > indegree:
            result.append(vertices[v])

    return result, len(result)

复杂度分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)，忽略输出结果

易错点

• 邻接矩阵中“行对应出度，列对应入度”。
• 有向图的入度和出度不是一回事，不能混着统计。
• 若矩阵元素不一定是 0/1，而是边权，需先明确题目是否只统计有边与否。

对应题

未找到高度一致的公开原题。

难度

⭐️