查找边[python]列表中有多少重复连接

Question

给出一系列的边，例如，

edges = [[1, 2], [1, 3], [2, 3], [4, 5], [4, 6], [5, 6], [10, 11], [12, 9], [12, 10]]

我需要找到列表中有多少重复连接。

在本例中:连接按顺序进行。

dup = 0

1-2

1-2-3

然后[2,3]已经连接，所以我们将dup增加1。

1-2-3, 4-5

1-2-3, 4-5-6

那么[5,6]已经连接了，所以我们再一次增加dup 1

1-2-3, 4-5-6, 10-11

1-2-3, 4-5-6, 9-12, 10-11

1-2-3, 4-5-6, 9-10-11-12 

返回dup = 2

最后一步是我的方法出错的地方，因为它将[12,10]计算为重复，因为我的当前方法是将数字添加到字典中，并检查x和y是否都在字典中，然后将dup增加1。

但是我真正需要做的是检查x和y是否已经连接，如果它们是增量dup 1。

但我被困在想办法来做这件事。

Answer 1

在研究这个问题时，我遇到了一个名为networkx的包。很明显，这个问题很简单。我喜欢90%的编程仅仅是依靠聪明人来做所有的艰苦工作，因为我肯定做不到。

import networkx as nx

def find_duplicate_edges(edges):
    graph = nx.Graph()
    for n1, n2 in edges:
        if graph.has_node(n1) and graph.has_node(n2) and nx.has_path(graph, n1, n2):
            yield n1, n2
        else:
            graph.add_edge(n1, n2)

if __name__ == '__main__':
    edges = [[1, 2], [1, 3], [2, 3], [4, 5], [4, 6], [5, 6], [10, 11], [12, 9], [12, 10]]
    for edge in find_duplicate_edges(edges):
        print(edge)

输出

(2, 3)
(5, 6)

Answer 2

在我看来，你基本上有一个邻接表，你需要的是一个邻接矩阵。我会这样做：

1. 制作一个二维数组(这是邻接矩阵).例如，这将是一个12x12矩阵。用所有假值初始化矩阵
2. 对于每个边，为相应的位置输入一个真值(即，对于1,2，在位置1、2和2，1中输入True )
3. 现在，您还需要标记间接连接。对于1,2的新True条目，您将在第2行中找到所有的True值，并将第1行中的相应值设置为True (反之亦然)。

注意:在更新表之前，通过检查第1行和第2行均为True的位置来检查重复项