Mastering Algorithms for Problem Solving in Python/

...

/

Unweighted Graphs: Breadth-First Search

Unweighted Graphs: Breadth-First Search

Learn about the breadth-first search algorithm and its applications in solving the shortest paths problem in unweighted graphs.

We'll cover the following...

Implementation of breadth-first search

In the simplest special case of the shortest path problem, all edges have weight 1, and the length of a path is just the number of edges. This special case can be solved by a species of our generic graph-traversal algorithm called breadth-first search. Breadth-first search is often attributed to Edward Moore, who described it in 1957 (as “Algorithm A”) as the first published method to find the shortest path through a maze. Especially in the context of VLSI wiring and robot path planning, breadth-first search is sometimes attributed to Chin Yang Lee, who described several applications of Moore’s “Algorithm A” (with proper credit to Moore) in 1961. However, in 1945, more than a decade before Moore considered mazes, Konrad Zuse described an implementation of breadth-first search as a method to count and label the components of a disconnected graph.

Breadth-first search maintains a first-in-first-out queue of vertices, which initially contains only the source vertex ss. At each iteration, the algorithm pulls a vertex uu from the front of the queue and examines each of its outgoing edges u→vu\rightarrow v. Whenever the algorithm discovers an outgoing tense edge u→vu\rightarrow v, it relaxes that edge and pushes vertex vv onto the queue. The algorithm ends when the queue becomes empty.

Algorithm

BFS(s)‾InitSSSP(s)Push(s)while the queue is not emptyu←Pull()for all edges u→vif dist(v)>dist(u)+1<< if u→v is tense >>dist(v)←dist(u)+1pred(v)←u<< relax u→v >>Push(v)\underline{BFS(s)} \\ \hspace{0.4cm} InitSSSP(s) \\ \hspace{0.4cm} Push(s) \\ \hspace{0.4cm} while\space the\space queue\space is\space not\space empty \\ \hspace{1cm} u←Pull() \\ \hspace{1cm} for\space all\space edges\space u\rightarrow v \\ \hspace{1.7cm} if\space dist(v) > dist(u) + 1 \hspace{1cm} {\color{Red} \left< \left<\space if\space u\rightarrow v \space is\space tense \space \right > \right >} \\ \hspace{2.3cm} dist(v) ← dist(u) + 1 \\ \hspace{2.3cm} pred(v) ← u \hspace{2.1cm} {\color{Red} \left< \left<\space relax\space u\rightarrow v \space\right > \right >} \\ \hspace{2.3cm} Push(v)

Implementation

Press + to interact
from typing import List
from queue import Queue
INF = int(1e9)
MAXN = 100005
adj = [[] for _ in range(MAXN)]   # adjacency list of the graph
dist = [INF] * MAXN
pred = [-1] * MAXN
visited = [False] * MAXN
def InitSSSP(s: int) -> None:
    global dist, pred, visited
    dist = [INF] * MAXN
    pred = [-1] * MAXN
    visited = [False] * MAXN
    dist[s] = 0
def Push(s: int, q: Queue) -> None:
    q.put(s)
    visited[s] = True
def BFS(s: int) -> None:
    InitSSSP(s)
    q = Queue()
    Push(s, q)
    while not q.empty():
        u = q.get()
        for v in adj[u]:
            if dist[v] > dist[u] + 1:
                # u->v is tense
                dist[v] = dist[u] + 1
                pred[v] = u     # relax u->v
                if not visited[v]:
                    # add v to queue
                    Push(v, q)
# example usage
adj[1].append(2)
adj[1].append(3)
adj[2].append(4)
adj[3].append(4)
BFS(1)
for i in range(1, 5):
    print("Shortest distance from 1 to", i, ":", dist[i])

Explanation

  • Lines 12: This line defines a function called InitSSSP that takes an integer s as an argument and returns None.
  • Lines 19: This line defines a function called Push that takes an integer s and a queue object q as arguments and returns None.
  • Lines 39–42: We create an example graph.

Modifications of breadth-first search

Breadth-first search is somewhat easier to analyze if we break its execution into phases by introducing an imaginary token. Before we pull any vertices, we push the token into the queue. The current phase ends when we pull the token out of the queue; we begin the next phase when we push the token into the queue again. Thus, the first phase consists entirely of scanning the source vertex ss. The algorithm ends when the queue contains only the token. The modified algorithm is shown below, and the illustration shows an example of this algorithm in action. Let us emphasize that these modifications are merely a convenience for analysis; with or without the token, the algorithm pushes and pulls vertices in the same order, scans edges in the same order, and outputs exactly the same distances and predecessors.

Algorithm

BFSWithToken(s):‾InitSSSP(s) ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy