在有向图中，了解每个顶点的度数是非常关键的。这是因为顶点的度数直接反映了它在图中的连接程度。在这个文章中，我们将探讨如何计算有向图中每个顶点的出度和入度。
出度和入度
首先，我们需要明确出度和入度的概念。
- 出度：一个顶点的出度指的是从该顶点出发，指向其他顶点的边的数量。
- 入度：一个顶点的入度则是指指向该顶点的边的数量。
例如，如果我们有一个有向图，顶点为A、B、C、D，边为(A, B)、(B, C)、(C, D)、(D, A)，那么我们可以得出以下度数：
- A的出度为2，因为从A出发的边有两条：A到B和A到D。
- A的入度为0，因为没有边是从其他顶点指向A。
- B的出度为1，只有一条边从B指向C。
- B的入度为1，因为只有一条边指向B，即A到B。
- C的出度为1，只有一条边从C指向D。
- C的入度为1，因为只有一条边指向C，即B到C。
- D的出度为1，只有一条边从D指向A。
- D的入度为2，因为两条边指向D，即C到D和A到D。
计算步骤
为了计算一个有向图中各顶点的度数，我们可以遵循以下步骤：
1. 初始化
首先，我们需要初始化一个数据结构来存储每个顶点的度数。这通常是一个字典，其中键是顶点，值是该顶点的度数。
# 初始化顶点的度数字典
degree = {vertex: 0 for vertex in vertices}
2. 遍历图
接下来，我们需要遍历图中的所有边。对于每条边，我们更新起点的出度和终点的入度。
for edge in edges:
start_vertex, end_vertex = edge
degree[start_vertex] += 1
degree[end_vertex] += 1
3. 输出结果
遍历所有边后，degree 字典中的值就是每个顶点的度数。我们可以简单地打印出这个字典来查看结果。
print(degree)
以上代码假设vertices是顶点集合，edges是边的列表，其中每条边都是一个元组，表示边的起点和终点。
通过这种方式，我们可以准确地计算并了解有向图中每个顶点的度数，这对于分析图的结构和功能非常有帮助。