🏷️ 知识点：入度
课后题 年第 8 题
数据结构
选择题
在含有 n 个顶点的简单有向图中，单个顶点的总度（入度与出度之和）最大为（ ）。
A. n B. n−1 C. 2n D. 2n−2
[tag_link]
正确答案：D
结论
单个顶点的总度最大为 2n−2。
推导
简单有向图没有自环和重边。对任一顶点，最多向其余 n−1 个顶点各发出一条边，出度至多 n−1；其余顶点也最多各有一条边指向它，入度至多 n−1。因此总度上界为 (n−1)+(n−1)=2n−2，且可同时达到。
易错点
不要只计算出度 n−1；题目问的是入度加出度。也不要把无向图的度数上界直接套到有向图。
课后题 年第 19 题
数据结构
选择题
带权有向图 (G) 用邻接矩阵存储，约定无边位置为 (\infty)（对角线为 0），则顶点 (v_i) 的入度等于邻接矩阵中（ ）。
A. 第 (i) 行非 (\infty) 的元素个数 B. 第 (i) 列非 (\infty) 的元素个数 C. 第 (i) 行非 (\infty) 且非 0 的元素个数 D. 第 (i) 列非 (\infty) 且非 0 的元素个数
[tag_link]
正确答案：D
结论
答案为 D：扫描第 (i) 列，统计既不是 (\infty) 又不是 0 的元素。
推导
邻接矩阵的第 (j) 行第 (i) 列元素表示边 (v_j\to v_i) 的权值。第 (i) 列中每个有限且非零的权值对应一条进入 (v_i) 的边，因此其个数就是入度；第 (i) 行统计的是出度。
易错点
入度与出度的方向相反：入度看列，出度看行。带权矩阵中不能只判断“非 (\infty)”——对角线的 0 表示无自环，必须同时排除 0。