如何在不重复的情况下列出边？

Question

我创建了一个函数来列出图形的所有边。我需要有关如何修改我的代码以获得正确输出的帮助 没有边缘重复 。这是我尝试过的：

def edges(A):
    node_list = [ ]
    for vertex in A:
        for neighb in A[ vertex ]:
              node_list.append(( vertex, neighb ))

    return(node_list)

data = {
    'A' : ['A', 'B', 'C'],
    'B' : ['C','A'],
    'C' : ['C', 'D'],
    'D' : ['E'],
    'E' : []
}

print("List of edges: ", edges(data))

输出：

[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'C'), 
('B', 'A'), ('C', 'C'), ('C', 'D'), ('D', 'E')]

Answer 1

idk 关于 python 但您可以为具有默认值 false.If 的边保留一个布尔值 isTraversed 遍历的 egde 将值更改为 true。在 if 语句中，如果 isTraversed 值为 false，则可以打印边缘。

Answer 2

一个简单的解决方案是使用一个集合来存储边，并保持每个边在内部排序（即，字典序值较低的节点将排在第一位）。使用集合，您不会有重复的边，并且在内部对每个边进行排序将有助于避免同时保留 (A, B) 和 (B, A)。在有向图的情况下，您可以跳过节点排序部分。 Python 实施：

def edges(A):
    edges = set()
    for vertex in A:
        for neighb in A[vertex]:
            first = min(vertex, neighb)
            second = neighb if first == vertex else vertex
            edges.add((first, second))

    return list(edges)

data = {
    'A' : ['A', 'B', 'C'],
    'B' : ['C','A'],
    'C' : ['C', 'D'],
    'D' : ['E'],
    'E' : []
}

print("List of edges: ", edges(data))

如何在不重复的情况下列出边？

How do I list edges without repetition?

graph-theory

python-3.x