graphs.breadth_first_search_2

https://en.wikipedia.org/wiki/Breadth-first_search pseudo-code: breadth_first_search(graph G, start vertex s): // all nodes initially unexplored mark s as explored let Q = queue data structure, initialized with s while Q is non-empty:

remove the first node of Q, call it v for each edge(v, w): // for w in graph[v]

if w unexplored:

mark w as explored add w to Q (at the end)

Attributes

G

Functions

benchmark_function(→ None)

breadth_first_search(→ list[str])

Implementation of breadth first search using queue.Queue.

breadth_first_search_with_deque(→ list[str])

Implementation of breadth first search using collection.queue.

Module Contents

graphs.breadth_first_search_2.benchmark_function(name: str) → None

Implementation of breadth first search using queue.Queue.

>>> ''.join(breadth_first_search(G, 'A'))
'ABCDEF'
graphs.breadth_first_search_2.breadth_first_search_with_deque(graph: dict, start: str) → list[str]

Implementation of breadth first search using collection.queue.

>>> ''.join(breadth_first_search_with_deque(G, 'A'))
'ABCDEF'
graphs.breadth_first_search_2.G