python - 拓扑排序 python 实现中的错误

Question

我刚刚用 Python 编写了一些代码，用于在给定无向图的情况下进行拓扑排序。

G = {
    7: [11, 8],
    5: [11],
    3: [8, 10],
    11: [2, 9],
    8: [9],
    2: [],
    9: [],
    10: []
}

class GraphException(Exception):
    def __init__(self, str):
        pass

def has_incoming_edges(g, a_node):
    """
    Return True if it has incoming edges,
    False otherwise.
    """
    for each_node in g:
        if a_node in g[each_node]:
            return True
    return False

def remove_edge(g, start, end):
    """
    Removes the edge start->end in g.
    """
    edges = g[start]
    edges.pop(edges.index(end))

def edges_exist(g):
    for each_node in g:
        if g[each_node]: return True
    return False

def do_topsort(g):
    S = [] # list of all nodes that have no incoming nodes
    L = [] # topordering

    for each_node in G:
        if not has_incoming_edges(g, each_node):
            S.append(each_node)

    while S:
        a_node = S.pop(0)
        print "Popping", a_node
        L.append(a_node)
        x = g[a_node]
        #TODO NEVER ITERATE ON A LIST AND REMOVE FROM IT AT
        # THE SAME TIME
        backup = g[a_node]
        for each_connected in backup:
            print ">>>", backup

            print "Removing edge", a_node, each_connected
            # Remove the edge from a_node to each_connected
            remove_edge(g, a_node, each_connected)

            print g

            if not has_incoming_edges(g, each_connected):
                print "Adding", each_connected
                S.append(each_connected)

    if edges_exist(g):
        print g
        print L
        raise GraphException("Graph has cycles")
    return L

def main():
    global G
    topsort = do_topsort(G)
    print topsort

if __name__ == '__main__':
    main()

我从这段代码中获得的输出如下:-

Popping 3
>>> [8, 10]
Removing edge 3 8
{2: [], 3: [10], 5: [11], 7: [11, 8], 8: [9], 9: [], 10: [], 11: [2, 9]}
Popping 5
>>> [11]
Removing edge 5 11
{2: [], 3: [10], 5: [], 7: [11, 8], 8: [9], 9: [], 10: [], 11: [2, 9]}
Popping 7
>>> [11, 8]
Removing edge 7 11
{2: [], 3: [10], 5: [], 7: [8], 8: [9], 9: [], 10: [], 11: [2, 9]}
Adding 11
Popping 11
>>> [2, 9]
Removing edge 11 2
{2: [], 3: [10], 5: [], 7: [8], 8: [9], 9: [], 10: [], 11: [9]}
Adding 2
Popping 2
{2: [], 3: [10], 5: [], 7: [8], 8: [9], 9: [], 10: [], 11: [9]}
[3, 5, 7, 11, 2]
Traceback (most recent call last):
  File "topsort.py", line 80, in <module>
    main()
  File "topsort.py", line 76, in main
    topsort = do_topsort(G)
  File "topsort.py", line 71, in do_topsort
    raise GraphException("Graph has cycles")
__main__.GraphException

请注意，在输出中有一行 Popping 7。它表示 7 是 for 循环 for each_connected in backup: 中正在处理的节点。我们可以看到 7 连接到 11 和 8。但是，该循环似乎只运行一次并删除边 7-11。节点 8 似乎没有被处理。我做错了什么？

Answer 1

您正在迭代并从备份中删除元素，因此您最终删除了错误的元素，使用反向:

for each_connected in reversed(backup):

或者复制列表:

for each_connected in backup[:]:

您还可以从类中删除 init 方法:

class GraphException(Exception):
    pass