A generic breadth first traversal function - Printable Version +- Python Forum ( https://python-forum.io)+-- Forum: General ( https://python-forum.io/Forum-General)+--- Forum: Completed Scripts/Snippets ( https://python-forum.io/Forum-Completed-Scripts-Snippets)+--- Thread: A generic breadth first traversal function ( /Thread-A-generic-breadth-first-traversal-function) |

A generic breadth first traversal function - Gribouillis - Jul-07-2019 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() Edit: A small improvement of version 2019.07.07 is to postpone the call to neighbors() as much as possible. RE: A generic breadth first traversal function - perfringo - Jul-11-2019 Just for historical reference I add link to Guido van Rossum essay Python Patternsâ€”Implementing Graphs RE: A generic breadth first traversal function - rootVIII - Jul-12-2019 ah more_itertools is pretty neat |