按BFS/DF排序边

Question

我正在处理一个边排序的问题，其中边以元组形式存储(node_i, node_j)，如下所示

>> edgeLst
>> [('123','234'),
    ('123','456'),
    ('123','789'),
    ('456','765'),
    ('456','789')
    ('234','765')]

注意边是唯一的，如果看到('123', '234')，就不会看到('234', '123')（图是无向的）。图中可能有一个循环。由于这个图非常大，有没有人能告诉我一种有效的方法，用一个给定的开始节点对BFS和DFS中的边进行排序，例如'123'？你知道吗

演示输出：

>> edgeSorting(input_lst=edgeLst, by='BFS', start_node='123')
>> [('123','234'),
    ('123','456'),
    ('123','789'),
    ('234','765')
    ('456','765'),
    ('456','789')]

Answer 1

以下是如何为BFS和DFS执行此操作：

from collections import defaultdict
def sorted_edges(input_lst, by, start_node):
    # Key the edges by the vertices
    vertices = defaultdict(lambda: [])
    for u, v in input_lst:
        vertices[u].append(v)
        vertices[v].append(u)
    if by == 'DFS':
        # Sort the lists
        for lst in vertices:
            lst = sorted(lst)
        # Perform DFS
        visited = set()
        def recurse(a):
            for b in vertices[a]:
                if not (a, b) in visited:
                    yield ((a,b))
                    # Make sure this edge is not visited anymore in either direction
                    visited.add((a,b))
                    visited.add((b,a))
                    for edge in recurse(b):
                        yield edge
        for edge in recurse(start_node):
            yield edge
    else: #BFS
        # Collect the edges
        visited = set()
        queue = [start_node]
        while len(queue):
            for a in queue: # Process BFS level by order of id
                level = []
                for b in vertices[a]:
                    if not (a, b) in visited:
                        yield ((a,b))
                        # Add to next level to process
                        level.append(b)
                        # Make sure this edge is not visited anymore in either direction
                        visited.add((a,b))
                        visited.add((b,a))
            queue = sorted(level)


edgeLst = [('123','234'),
('123','456'),
('123','789'),
('456','765'),
('456','789'),
('234','765')]

print (list(sorted_edges(edgeLst, 'DFS', '123')))

在Python 3中，可以简化：

for edge in recurse(b):
    yield edge

收件人：

yield from recurse(b)

。。。和start_node一样。你知道吗