邻接表上实现
拓扑排序的步骤如下：
1. 首先，需要统计每个顶点的入度，即有多少条边指向该顶点。可以通过遍历
邻接表，记录每个顶点的入度。
2. 接下来，需要将入度为0的顶点加入拓扑序列中。可以使用一个
队列来存储入度为0的顶点。
3. 然后，从
队列中取出一个顶点，将其所有邻接点的入度减1。如果邻接点的入度为0，则将其加入
队列中。
4. 重复步骤3，直到
队列为空。如果此时拓扑序列中的顶点数小于图中的顶点数，则说明图中存在环。
下面是一个Python实现的例子：
```python
from collections import deque
def topo_sort(graph):
# 统计每个顶点的入度
in_degree={v: 0 for v in graph}
for v in graph:
for w in graph[v]:
in_degree[w] +=1
# 将入度为0的顶点加入
队列
queue=deque([v for v in in_degree if in_degree[v]==0])
# 依次取出
队列中的顶点，并将其邻接点的入度减1
topo_order=[]
while queue:
v=queue.popleft()
topo_order.append(v)
for w in graph[v]:
in_degree[w] -=1
if in_degree[w]==0:
queue.append(w)
# 如果拓扑序列中的顶点数小于图中的顶点数，则说明图中存在环
if len(topo_order) < len(graph):
return None
else:
return topo_order
```
/7861839adfb50c383118c9b827ceb570.jpeg)
