有向图的逆邻接表求入度
时间: 2023-12-18 09:28:50 浏览: 113
dsf.rar_有向图邻接表_有向邻接表
有向图的逆邻接表是指对于有向图中的每个顶点,建立一个链表存储所有指向该顶点的顶点。因此,对于一个顶点的入度,只需要统计该顶点在逆邻接表中的链表中的节点数即可。
以下是求有向图指定顶点入度的Python代码示例,其中graph为有向图的邻接表表示,vertex为指定的顶点:
```python
def get_indegree(graph, vertex):
if vertex not in graph:
return -1
indegree = 0
for node in graph:
for neighbor in graph[node]:
if neighbor == vertex:
indegree += 1
return indegree
```
阅读全文