求k个DAG的随机拓扑排序

import random

def topological_sort(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    
    queue = [u for u in in_degree if in_degree[u] == 0]
    result = []
    
    while queue:
        u = queue.pop(0)
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    return result

def random_topological_sort(graph, k):
    sorted_graphs = [topological_sort(graph) for _ in range(k)]
    random.shuffle(sorted_graphs)
    return sorted_graphs

# 示例DAG
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

# 获取k个随机拓扑排序
k = 3
sorted_results = random_topological_sort(graph, k)
for i, result in enumerate(sorted_results):
    print(f"Random Topological Sort {i+1}: {result}")

random.seed(42)  # 设置随机种子