BreadthFirstSearch module¶

The breadth first search finds the shortest path from a given vertex to every other vertex in an unweighted simple graph.

A breadth first search uses a queue, a First-In-First-Out (FIFO) data structure, to find the shortest number of edges needed to make a uv-path from the start vertex u to any other vertex v in the graph. While there are unprocessed vertices, we pop them off the queue and test to see if we know the distance they are from vertex u. If that distance is still infinity we add them to the queue and update the distance to be one father than the current vertex we are processing.

Algorithm 2.4.1 on page 52, however we are using a true queue rather than an array processed in queue order.

BreadthFirstSearch.bfs(G, u)¶

Perform a breadth first search over G starting at u

Parameters

Gnx.Graph

The graph we wish to search

uint

The origin vertex from which the search starts

Returns

List

A list dist where dist[v] is the distance of the shortest path from u to v. Note, dist[u] = 0

BreadthFirstSearch.print_bfs_dist(G, u)¶

Perform a breadth first search over G starting with u and print the results.

Parameters

Gnx.Graph

The graph we wish to search.

uint

The origin vertex from which the search starts.

Examples

>>> print_bfs_dist(graph, 0)
Vertex 0: Dist(0, 0) = 0
Vertex 1: Dist(0, 1) = 1
Vertex 2: Dist(0, 2) = 1
Vertex 3: Dist(0, 3) = 1
Vertex 4: Dist(0, 4) = 2
Vertex 5: Dist(0, 5) = 2
Vertex 6: Dist(0, 6) = 2
Vertex 7: Dist(0, 7) = 2
Vertex 8: Dist(0, 8) = 2
Vertex 9: Dist(0, 9) = 2

Result of a breadth first search on the petersen graph.