0

所以我想写一个代码来做无环图的传递减少。所以元素是：

(3, 5), (5, 2), (2, 1), (4, 2), (3, 1), (4, 1)

这是我到目前为止所写的：

graph = [[3, 5],[5, 2],[2, 1],[4, 2],[3, 1],[4, 1]]

for i in range(len(graph)):
    for j in range(len(graph)):
        for k in range(len(graph)):
            if [i,j] in graph and [j,k] in graph:
                a = [i,k]
                graph.pop(a)
print(graph)

运行后，我希望删除 (4,1) 后得到以下内容：

>> (3, 5), (5, 2), (2, 1), (4, 2), (3, 1)

但相反，它返回：

>> (3, 5), (5, 2), (2, 1), (4, 2), (3, 1), (4, 1)

我无法弄清楚我做错了什么。如果有人能指出错误，那就太好了！

PS：传递减少是删除图的冗余边。例如：

如果 ( A -> B ) 和 ( B -> C )，则 ( A -> C )，换句话说：如果 A 连接到 B 并且 B 连接到 C，那么 A 也连接到 C。并且在这种情况（ A -> C ）是多余的，因为 A 可以通过 B 到达 C 因此应该被删除。

4

1 回答 1

1

我改进了你的代码，我添加了一个条件if a in graph:，因为在某些情况下会出现传递减少并且元素 [i,k] 不存在。该函数还pop()按索引删除元素，而不是按对象（如remove().

graph = [[3, 5],[5, 2],[2, 1],[4, 2],[3, 1],[4, 1]]

for i in range(len(graph)):
    for j in range(len(graph)):
        for k in range(len(graph)):
            if [i,j] in graph and [j,k] in graph:
                a = [i,k]
                if a in graph:
                    graph.remove(a)
print(graph)

我希望这可以帮助你。

于 2016-08-24T17:20:29.060 回答