图的度：数一数你的朋友有几个？

在图中，每个顶点（可以理解成一个人、一个城市、一个游戏角色）都会和一些边相连。一个顶点连接了多少条边，这个数量就叫它的“度”。比如，在班级关系图里，小明的微信好友有5个同学，那么小明的度就是5。度能帮我们快速了解一个顶点在图中“有多活跃”——朋友多的人度大，朋友少的人度小。

对于有方向的图（有向图），度还要分成两种：出度和入度。出度是从自己出发指向别人的箭头数，入度是从别人指向自己的箭头数。就像在“谁给谁送零食”的关系里，你送出去多少零食（出度），别人送给你多少零食（入度）。

下面我们一步步来看如何计算图的度。

1. 无向图的度

在无向图中，边没有方向，你连着我，我连着你。所以每个顶点的度就是它直接连接的其他顶点的数量。

生活例子：假设你有一个小班，班上5个同学，用数字1~5表示。谁和谁是好朋友，我们就画一条无向边。比如：

1和2是朋友
1和3是朋友
2和3是朋友
4和5是朋友

那么顶点1的度是2（连了2和3），顶点2的度是2，顶点3的度是2，顶点4的度是1，顶点5的度是1。

计算方式：直接用邻接表表示图，每个顶点对应一个列表，列表的长度就是该顶点的度。注意：无向图的邻接表中，每条边会被两个顶点各存一次，所以长度就是邻居个数。

下面代码演示如何计算无向图中每个顶点的度：

# 无向图的邻接表
graph = {
    1: [2, 3],     # 顶点1的朋友是2和3
    2: [1, 3],     # 顶点2的朋友是1和3
    3: [1, 2],     # 顶点3的朋友是1和2
    4: [5],        # 顶点4的朋友只有5
    5: [4]         # 顶点5的朋友只有4
}

# 遍历每个顶点，计算度
for vertex in graph:
    degree = len(graph[vertex])  # 列表长度就是度
    print(f"顶点{vertex}的度 = {degree}")

输出：

顶点1的度 = 2
顶点2的度 = 2
顶点3的度 = 2
顶点4的度 = 1
顶点5的度 = 1

2. 有向图的出度和入度

有向图的边有方向，用箭头表示。一个顶点指向别人的箭头数叫“出度”，别人指向它的箭头数叫“入度”。总度数 = 出度 + 入度。

生活例子：想象一个“零食传递”游戏，每个同学可以把自己的一包薯片送给另一个同学（只能送一次）。我们用有向图表示：

1 → 2（1送给2）
2 → 3（2送给3）
3 → 1（3送给1）
4 → 1（4也送给1）

那么顶点1：出度是0（它没送给别人），入度是2（2和3都送给了它？不对，这里是3→1和4→1，所以入度是2）。顶点2：出度是1（送给3），入度是1（1送给它）。顶点3：出度是1（送给1），入度是1（2送给它）。顶点4：出度是1（送给1），入度是0。

计算方式：

出度：统计该顶点的邻接表列表长度，因为列表里存的是它指向的顶点。
入度：需要遍历所有顶点，看看哪些箭头指向了该顶点。我们可以用一个字典记录每个顶点的入度，初始为0，然后遍历每个顶点的邻居，每遇到一个邻居，就把邻居的入度加1。

下面代码演示有向图出度和入度的计算：

# 有向图的邻接表（箭头方向：key -> values）
digraph = {
    1: [2],       # 顶点1指向顶点2
    2: [3],       # 顶点2指向顶点3
    3: [1],       # 顶点3指向顶点1
    4: [1]        # 顶点4指向顶点1
}

# 计算出度：每个顶点列表的长度
out_degree = {}
for v, neighbors in digraph.items():
    out_degree[v] = len(neighbors)  # 出度

# 计算入度：先初始化入度为0
in_degree = {}
for v in digraph:
    in_degree[v] = 0

# 遍历所有顶点，统计入度
for v in digraph:
    for neighbor in digraph[v]:   # 对于v指向的每个邻居
        in_degree[neighbor] += 1  # 该邻居的入度加1

# 输出结果
print("出度:", out_degree)
print("入度:", in_degree)
# 也可以顺便输出总度数：出度+入度
total_degree = {}
for v in digraph:
    total_degree[v] = out_degree[v] + in_degree[v]
print("总度数:", total_degree)

输出：

出度: {1: 1, 2: 1, 3: 1, 4: 1}
入度: {1: 2, 2: 1, 3: 1, 4: 0}
总度数: {1: 3, 2: 2, 3: 2, 4: 1}

3. 新手容易犯的错误

把有向图当成无向图算度：比如上面有向图例子中，如果错误地用列表长度当作总度数，就会得到顶点1的度是1（实际上它的总度是3），因为漏算了入度。所以一定要区分图是否有方向。
忘记处理孤立顶点：如果一个顶点没有任何边（比如图中只有顶点5但没有出现在任何边里），它的度是0。在邻接表表示中，需要把它也放进字典，并给一个空列表。
入度累加时忘了初始化：有些同学直接用 defaultdict 或者初始化字典为0，如果不初始化，直接对不存在的键 +=1 会报 KeyError。
混淆“邻居”和“度”：在无向图中，自己的邻居数就是度；但在有向图中，邻居可能是出度指向的目标，但入度不是邻居数，需要额外统计。

4. 完整可运行示例

下面用一个贴近学生生活的“零花钱交易”例子，综合展示无向图和有向图的度计算。假设一个小组有5个同学，记录他们互相借零花钱的关系（无向）和买零食的请客关系（有向）。

# 示例：同学之间的零花钱借贷（无向图）
# 好朋友之间借钱，边表示互相借过钱
borrow_graph = {
    1: [2, 3],        # 1和2、3借过钱
    2: [1, 4],        # 2和1、4借过钱
    3: [1],           # 3只和1借过钱
    4: [2, 5],        # 4和2、5借过钱
    5: [4]            # 5和4借过钱
}

print("=== 无向图（借钱关系）的度 ===")
for vertex in borrow_graph:
    degree = len(borrow_graph[vertex])
    print(f"同学{vertex}的借贷度 = {degree} (认识{degree}个债主/债民)")

# 示例：同学之间请客吃零食（有向图）
# 箭头表示谁请谁，比如 1->2 表示1请了2吃零食
treat_graph = {
    1: [2, 3],        # 1请了2和3
    2: [3],           # 2请了3
    3: [4],           # 3请了4
    4: [1],           # 4请了1
    5: []             # 5谁也没请（但可能被请）
}

# 计算入度
in_degree_t = {v: 0 for v in treat_graph}  # 初始化入度为0
for v in treat_graph:
    for target in treat_graph[v]:
        in_degree_t[target] += 1

print("\n=== 有向图（请客关系）的度 ===")
print("出度（请过多少人）:", {v: len(neighbors) for v, neighbors in treat_graph.items()})
print("入度（被请次数）:", in_degree_t)
# 计算总度数（请客+被请的次数总和）
total_t = {}
for v in treat_graph:
    out_ = len(treat_graph[v])
    in_ = in_degree_t[v]
    total_t[v] = out_ + in_
    print(f"同学{v}: 出度={out_}, 入度={in_}, 总度={total_t[v]}")

运行结果：

=== 无向图（借钱关系）的度 ===
同学1的借贷度 = 2 (认识2个债主/债民)
同学2的借贷度 = 2
同学3的借贷度 = 1
同学4的借贷度 = 2
同学5的借贷度 = 1

=== 有向图（请客关系）的度 ===
出度（请过多少人）: {1: 2, 2: 1, 3: 1, 4: 1, 5: 0}
入度（被请次数）: {1: 1, 2: 1, 3: 2, 4: 1, 5: 0}
同学1: 出度=2, 入度=1, 总度=3
同学2: 出度=1, 入度=1, 总度=2
同学3: 出度=1, 入度=2, 总度=3
同学4: 出度=1, 入度=1, 总度=2
同学5: 出度=0, 入度=0, 总度=0

5. 相关指引

图的存储方式：除了邻接表，还有邻接矩阵。对于无向图，邻接矩阵是对称的；有向图不对称。度可以通过矩阵的行和列求和得到。
握手定理：在无向图中，所有顶点的度数之和等于边数的两倍（因为每条边贡献两度）。在有向图中，所有顶点的出度之和等于入度之和，也等于边数。
图的遍历：深度优先搜索（DFS）和广度优先搜索（BFS）中经常需要获取某个顶点的邻居，其实就是访问它的邻接表，而邻居数量就是度。理解度对编写图算法很有帮助。
特殊顶点：度数为0的顶点称为孤立点；在无向图中，度数为1的顶点称为叶子节点（常用于树结构）；在有向图中，出度为0的顶点称为“汇点”，入度为0的称为“源点”。

掌握了图的度，你就拿到了分析图结构的第一把钥匙。接下来可以学习如何用图表示真实世界的关系，比如社交网络、地图导航、游戏里的技能树等等。

Python图的度