Unweighted Graphs: Breadth-First Search

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

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
import java.util.*;
@SuppressWarnings("unchecked")
public class Main {
    private static final int INF = 1000000000;
    private static final int MAXN = 100005;
    private static ArrayList<Integer>[] adj = new ArrayList[MAXN];
    private static int[] dist = new int[MAXN];
    private static int[] pred = new int[MAXN];
    private static boolean[] visited = new boolean[MAXN];
    private static void InitSSSP(int s) {
        for (int i = 0; i < MAXN; i++) {
            dist[i] = INF;
            pred[i] = -1;
            visited[i] = false;
        }
        dist[s] = 0;
        visited[s] = true; // initialize starting node as visited
    }
    private static void Push(int s, Queue<Integer> q) {
        q.add(s);
        visited[s] = true;
    }
    private static void bfs(int s) {
        InitSSSP(s);
        Queue<Integer> q = new LinkedList<>();
        Push(s, q);
        while (!q.isEmpty()) {
            int u = q.remove();
            for (int v : adj[u]) {
                if (dist[v] > dist[u] + 1) {
                    // u->v is tense
                    dist[v] = dist[u] + 1;
                    pred[v] = u; // relax u->v
                    if (!visited[v]) {
                        // add v to queue
                        Push(v, q);
                    }
                }
            }
        }
    }
    public static void main(String[] args) {
        // example usage
        for (int i = 0; i < MAXN; i++) {
            adj[i] = new ArrayList<>();
        }
        adj[1].add(2);
        adj[1].add(3);
        adj[2].add(4);
        adj[3].add(4);
        bfs(1);
        for (int i = 1; i <= 4; i++) {
            System.out.println("Shortest distance from 1 to " + i + ": " + dist[i]);
        }
    }
}

Explanation

  • Line 2: The command @SuppressWarnings("unchecked") removes any unwanted warning that may appear during the compilation of the code.
  • Line 5: This line declares a constant variable named INF and initializes it with the value 1000000000.
  • Lines 23–26: In Dijkstra’s algorithm, when a vertex is visited for the first time, its neighbors can be added to the priority queue (in the order of increasing distance from the source vertex) for further processing. The Push function performs this task by adding a vertex s to the end of the queue q and setting its visited flag to true.
  • Lines 53–57: Add edges to the graph and then call the BFS algorithm with the starting node 1.

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 PushPushes and PullPull ...

Create a free account to access the full course.

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