Jul-07-2019, 06:51 AM
(This post was last modified: Jul-07-2019, 06:51 AM by Gribouillis.)
The function
breadth_first()
defined below generates the nodes of a directed graph in breadth first order. Repeated nodes are ignored: only the first occurrence is generated.from collections import deque from itertools import chain from more_itertools import unique_everseen __version__ = '2019.07.07.1' def consume(d, start, neighbors): yield (start,) while d: yield neighbors(d.popleft()) def breadth_first(start, neighbors): """Generates nodes of a directed graph in level order. Arguments: * start : an arbitrary initial element (any hashable object) * neighbors : a function such that neighbors(item) is a sequence of the item's neighbors in the graph. Returns: A sequence of nodes in level order. Duplicate nodes are ignored: only the first occurrence is generated. """ d = deque() for item in unique_everseen( chain.from_iterable(consume(d, start, neighbors))): yield item d.append(item) if __name__ == '__main__': D = { 1: [2, 3, 4], 2: [5, 6], 4: [7, 8], 5: [9, 10, 4], 7: [11, 12], } for x in breadth_first(1, lambda n: D.get(n, ())): print(x, end=' ') print()
Output:1 2 3 4 5 6 7 8 9 10 11 12
Edit: A small improvement of version 2019.07.07 is to postpone the call to neighbors() as much as possible.