使用python写一个求有向无环图所有可能的拓扑排序的代码
时间: 2024-03-10 16:45:05 浏览: 18
好的,以下是一个基于深度优先搜索的python代码,用于求有向无环图的所有拓扑排序:
```python
from collections import defaultdict
class DAG:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.vertices = vertices
def add_edge(self, u, v):
self.graph[u].append(v)
def dfs(self, visited, stack, u):
visited[u] = True
for v in self.graph[u]:
if not visited[v]:
self.dfs(visited, stack, v)
stack.append(u)
def topological_sort(self):
visited = {v: False for v in self.vertices}
stack = []
for v in self.vertices:
if not visited[v]:
self.dfs(visited, stack, v)
return stack[::-1]
def all_topological_sorts_util(self, visited, stack, all_sorts):
flag = False
for v in self.vertices:
if not visited[v] and not self.incoming_edges(v, visited):
visited[v] = True
stack.append(v)
self.all_topological_sorts_util(visited, stack, all_sorts)
visited[v] = False
stack.pop()
flag = True
if not flag:
all_sorts.append(stack[:])
def incoming_edges(self, v, visited):
count = 0
for u in self.vertices:
if visited[u] and v in self.graph[u]:
count += 1
return count
def all_topological_sorts(self):
visited = {v: False for v in self.vertices}
stack = []
all_sorts = []
self.all_topological_sorts_util(visited, stack, all_sorts)
return all_sorts
# 示例
if __name__ == "__main__":
g = DAG(['A', 'B', 'C', 'D'])
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
print("所有拓扑排序:")
print(g.all_topological_sorts())
```
在上面的示例中,我们创建了一个有向无环图,然后使用 `all_topological_sorts` 函数来获取所有可能的拓扑排序。请注意,如果图中存在环路,则无法进行拓扑排序。