python - 卡恩算法的顺序不正确

Question

我正在尝试使用卡恩算法实现拓扑排序：

from collections import defaultdict

def ordering(graph:dict):
    in_counts = defaultdict(int)
    for k, v in graph.items():
        if not k in in_counts:
            in_counts[k] = 0
        for in_node in v:
            in_counts[in_node] += 1

    queue = []
    for in_node in in_counts.keys():
        if in_counts[in_node] == 0:
            queue.append(in_node)

    topological_order = []

    while queue:
        print("in_counts:", in_counts)
        print("queue:", queue)
        current_node = queue.pop(0)
        topological_order.append(current_node)
        print("result:", topological_order)
        if not current_node in graph:
            continue
        for in_node in graph[current_node]:
            in_counts[in_node] -= 1
            if in_counts[in_node] == 0:
                queue.append(in_node)

    return topological_order

print(ordering({'GTTGA': ['CTGAG'], 'TTCAC': ['GTTGA'], 'AAGGC': ['GTTGA', 'TAACA', 'TTCAC'], 'CGGGC': ['GTTGA', 'TAACA'], 'CCCTC': ['GTTGA', 'TAACA', 'TTCAC', 'AAGGC', 'CGGGC', 'CTGAG'], 'AGCTT': ['GTTGA']}))

调试输出：

in_counts: defaultdict(<class 'int'>, {'GTTGA': 5, 'CTGAG': 2, 'TTCAC': 2, 'AAGGC': 1, 'TAACA': 3, 'CGGGC': 1, 'CCCTC': 0, 'AGCTT': 0})
queue: ['CCCTC', 'AGCTT']
result: ['CCCTC']
in_counts: defaultdict(<class 'int'>, {'GTTGA': 4, 'CTGAG': 1, 'TTCAC': 1, 'AAGGC': 0, 'TAACA': 2, 'CGGGC': 0, 'CCCTC': 0, 'AGCTT': 0})
queue: ['AGCTT', 'AAGGC', 'CGGGC']
result: ['CCCTC', 'AGCTT']
in_counts: defaultdict(<class 'int'>, {'GTTGA': 3, 'CTGAG': 1, 'TTCAC': 1, 'AAGGC': 0, 'TAACA': 2, 'CGGGC': 0, 'CCCTC': 0, 'AGCTT': 0})
queue: ['AAGGC', 'CGGGC']
result: ['CCCTC', 'AGCTT', 'AAGGC']
in_counts: defaultdict(<class 'int'>, {'GTTGA': 2, 'CTGAG': 1, 'TTCAC': 0, 'AAGGC': 0, 'TAACA': 1, 'CGGGC': 0, 'CCCTC': 0, 'AGCTT': 0})
queue: ['CGGGC', 'TTCAC']
result: ['CCCTC', 'AGCTT', 'AAGGC', 'CGGGC']
in_counts: defaultdict(<class 'int'>, {'GTTGA': 1, 'CTGAG': 1, 'TTCAC': 0, 'AAGGC': 0, 'TAACA': 0, 'CGGGC': 0, 'CCCTC': 0, 'AGCTT': 0})
queue: ['TTCAC', 'TAACA']
result: ['CCCTC', 'AGCTT', 'AAGGC', 'CGGGC', 'TTCAC']
in_counts: defaultdict(<class 'int'>, {'GTTGA': 0, 'CTGAG': 1, 'TTCAC': 0, 'AAGGC': 0, 'TAACA': 0, 'CGGGC': 0, 'CCCTC': 0, 'AGCTT': 0})
queue: ['TAACA', 'GTTGA']
result: ['CCCTC', 'AGCTT', 'AAGGC', 'CGGGC', 'TTCAC', 'TAACA']
in_counts: defaultdict(<class 'int'>, {'GTTGA': 0, 'CTGAG': 1, 'TTCAC': 0, 'AAGGC': 0, 'TAACA': 0, 'CGGGC': 0, 'CCCTC': 0, 'AGCTT': 0})
queue: ['GTTGA']
result: ['CCCTC', 'AGCTT', 'AAGGC', 'CGGGC', 'TTCAC', 'TAACA', 'GTTGA']
in_counts: defaultdict(<class 'int'>, {'GTTGA': 0, 'CTGAG': 0, 'TTCAC': 0, 'AAGGC': 0, 'TAACA': 0, 'CGGGC': 0, 'CCCTC': 0, 'AGCTT': 0})
queue: ['CTGAG']
result: ['CCCTC', 'AGCTT', 'AAGGC', 'CGGGC', 'TTCAC', 'TAACA', 'GTTGA', 'CTGAG']

预期结果是：

['CCCTC', 'CGGGC', 'AGCTT', 'AAGGC', 'TAACA', 'TTCAC', 'GTTGA', 'CTGAG']

这与我的结果不同（见上文）。

我知道CGGGC应该放在 之后CCCTC，但是我不明白这如何与算法不冲突：在开始时两者都具有，并且CCCTC在之后进入队列。AGCTT0CGGGCAGCTT

我错过了什么？

标签： pythongraph-algorithmtopological-sort