##### A generic breadth first traversal function
 A generic breadth first traversal function Posts: 2,813 Threads: 33 Joined: Jan 2018 Reputation: 256 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. Reply perfringo Da Bishop Posts: 1,634 Threads: 7 Joined: Jun 2018 Reputation: 156 Jul-11-2019, 12:54 PM Just for historical reference I add link to Guido van Rossum essay Python Patternsâ€”Implementing Graphs I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame. Reply rootVIII Not Blown Up Yet Posts: 69 Threads: 28 Joined: Aug 2018 Reputation: 2 Jul-12-2019, 12:26 AM ah more_itertools is pretty neat Reply

 Possibly Related Threads… Thread Author Replies Views Last Post general tree traversal cwilson1 2 2,381 Jun-19-2018, 03:46 PM Last Post: cwilson1

Forum Jump:

### User Panel Messages

##### Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020