求DAG所有可能的拓扑排序

对于一个有向无环图（DAG），可以通过拓扑排序得到其所有可能的拓扑排序。

拓扑排序的步骤如下：

1. 找到入度为0的节点，并将其加入拓扑序列中。

2. 将该节点指向的节点的入度减1。

3. 重复步骤1和2，直到所有节点都被加入拓扑序列中。

如果DAG中存在环路，则无法进行拓扑排序。

对于一个DAG，可能存在多种拓扑排序。下面是一个求解DAG所有可能拓扑排序的算法：

1. 对DAG进行拓扑排序，得到第一种拓扑序列。

2. 将第一种拓扑序列中的每个节点从DAG中删除，得到一个新的DAG。

3. 对新的DAG进行拓扑排序，得到第二种拓扑序列。

4. 将第二种拓扑序列中的每个节点从新的DAG中删除，得到一个新的DAG。

5. 重复步骤3和4，直到得到所有可能的拓扑排序。

下面是一个Python代码实现，用于求解DAG的所有可能拓扑排序：

from collections import defaultdict

def all_topological_sorts(graph):
    in_degree = defaultdict(int)
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    q = [u for u in graph if in_degree[u] == 0]
    result = []
    def dfs(path):
        if len(path) == len(graph):
            result.append(path)
            return
        for u in q:
            if u not in path:
                new_path = path + [u]
                new_q = q.copy()
                new_q.remove(u)
                for v in graph[u]:
                    in_degree[v] -= 1
                    if in_degree[v] == 0:
                        new_q.append(v)
                dfs(new_path)
                for v in graph[u]:
                    in_degree[v] += 1
        return
    dfs([])
    return result

其中，参数`graph`是一个字典，表示DAG中的节点和边。例如，`graph = {'A': {'B', 'C'}, 'B': {'D'}, 'C': {'D'}, 'D': set()}`表示DAG中有4个节点，分别是A、B、C、D，边的情况如下：

A -> B
A -> C
B -> D
C -> D

调用`all_topological_sorts(graph)`函数即可得到DAG的所有可能拓扑排序。