实现邻接链表和逆邻接链表两种求顶点入度的算法
时间: 2024-02-02 08:03:39 浏览: 77
实现邻接链表和逆邻接链表两种求顶点入度的算法:
邻接链表求顶点入度的算法:
1. 初始化一个长度为n的数组indegree,用于存储每个顶点的入度。
2. 遍历每个顶点的邻接表,将每个邻接点的入度加1。
3. 遍历indegree数组,输出指定顶点的入度。
逆邻接链表求顶点入度的算法:
1. 初始化一个长度为n的数组indegree,用于存储每个顶点的入度。
2. 遍历每个顶点的逆邻接表,将每个逆邻接点的入度加1。
3. 遍历indegree数组,输出指定顶点的入度。
示例代码如下:
```python
# 邻接链表求顶点入度
def get_indegree(graph, vertex):
n = len(graph)
indegree = [0] * n
for i in range(n):
for j in graph[i]:
if j == vertex:
indegree[i] += 1
return indegree[vertex]
# 逆邻接链表求顶点入度
def get_reverse_indegree(graph, vertex):
n = len(graph)
indegree = [0] * n
for i in range(n):
for j in graph[i]:
if i == vertex:
indegree[j] += 1
return indegree[vertex]
```
阅读全文