邻接表上实现
拓扑排序的步骤如下:
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
```