Python Data Structures and Algorithms

Breadth-first search

The breadth-first search algorithm starts at a node, chooses that node or vertex as its root node, and visits the neighboring nodes, after which it explores neighbors on the next level of the graph.

Consider the following diagram as a graph:

The diagram is an example of an undirected graph. We continue to use this type of graph to help make explanation easy without being too verbose.

The adjacency list for the graph is as follows:

    graph = dict()     graph['A'] = ['B', 'G', 'D']     graph['B'] = ['A', 'F', 'E']     graph['C'] = ['F', 'H']     graph['D'] = ['F', 'A']     graph['E'] = ['B', 'G']     graph['F'] = ['B', 'D', 'C']  graph['G'] ...