邻接表有向图入度计算
时间: 2023-11-27 22:43:11 浏览: 166
-针对一按照邻接表存放的有向图,计算图中节点的出度和入度
5星 · 资源好评率100%
邻接表表示的有向图,入度指的是以某个顶点为终点的边的数量。计算有向图的入度可以通过遍历所有顶点并统计以每个顶点为终点的边的数量来实现。
以下是计算有向图入度的一种简单算法:
1. 创建一个大小为顶点数量的数组 indegree,用于存储每个顶点的入度。
2. 遍历邻接表的所有顶点。
3. 对于每个顶点 v,遍历它的所有邻接顶点 w。
4. 对于每个邻接顶点 w,将 indegree[w] 的值加1。
5. 遍历完所有顶点后,indegree 数组中的每个元素即为对应顶点的入度。
以下是一个示例代码来计算有向图入度:
```python
def calculate_indegree(adjacency_list):
num_vertices = len(adjacency_list)
indegree = [0] * num_vertices # 创建一个大小为顶点数量的数组
for v in range(num_vertices):
for w in adjacency_list[v]:
indegree[w] += 1 # 将邻接顶点的入度加1
return indegree
# 示例邻接表
adjacency_list = [[1, 2], [2, 3], [0], [2]]
indegrees = calculate_indegree(adjacency_list)
print(indegrees) # 输出: [1, 1, 2, 0]
```
阅读全文