实现邻接链表和逆邻接链表两种求顶点入度的算法
时间: 2024-02-02 09:03:39 浏览: 28
实现邻接链表和逆邻接链表两种求顶点入度的算法:
邻接链表求顶点入度的算法:
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]
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)