0-1 BFS

Code in C++

Let’s have a look at the implementation of the above approach:

#include <bits/stdc++.h>
#define V 6
using namespace std;

struct node {
  int no, weight; // no denoted the node and weight denoted the weight of edges
};

vector <node> Edges[V]; // to store edges

void ZeroOneBFS(int src) {

  int dist[V];  

  for (int i = 0; i < V; i++)
      dist[i] = INT_MAX;

  deque <int> Q;

  dist[src] = 0;                  //distance from source to source is 0

  Q.push_back(src);

  while (!Q.empty()) {

      int v = Q.front();

      Q.pop_front();

      for (int i = 0; i < Edges[v].size(); i++) {

        if (dist[Edges[v][i].no] > dist[v] + Edges[v][i].weight) {

            dist[Edges[v][i].no] = dist[v] + Edges[v][i].weight;

            if (Edges[v][i].weight == 0)    //if 0 weight edge, store at front of deque

              Q.push_front(Edges[v][i].no);
            else
              Q.push_back(Edges[v][i].no);  // if 1 weight edge, store at back of deque
        }

      }

  }

  for (int i = 0; i < V; i++)
      cout << "Distance from the source node to " << i << ":" << "\t" << dist[i] << endl;
}

void insertEdge(int u, int v, int wt) {
  Edges[u].push_back({v, wt});
  Edges[v].push_back({u, wt});
}
int main() {
  insertEdge(0, 1, 0);
  insertEdge(0, 2, 1);
  insertEdge(1, 3, 1);
  insertEdge(3, 4, 0);
  insertEdge(4, 5, 1);
  insertEdge(5, 2, 1);

  int src = 0;
  ZeroOneBFS(src);
}

Output

Distance from the source node to 0: 0
Distance from the source node to 1: 0
Distance from the source node to 2: 1
Distance from the source node to 3: 1
Distance from the source node to 4: 1
Distance from the source node to 5: 2

Complexity Analysis

Time complexity

All nodes have been visited only once in this algorithm. As a result, the time complexity of 0-1 BFS is O(E + V), linear and faster than Dijkstra, which runs in O(E+VlogV).

Space complexity

As we store the graph in an adjacency list and maintain a deque and a distance array to store the distances of the nodes, the space complexity turns out to be O(V + E).

Read More - Time Complexity of Sorting Algorithms, Graph Traversal Techniques in DFS BFS

Implementation of 0-1 BFS on Java and Python3

import java.util.*;

class Main {
    static int V = 6;
    static ArrayList<Node>[] edges = new ArrayList[V];

    static class Node {
        int no, weight;

        Node(int no, int weight) {
            this.no = no;
            this.weight = weight;
        }
    }

    static void zeroOneBFS(int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);

        Deque<Integer> Q = new ArrayDeque<>();

        dist[src] = 0;
        Q.addLast(src);

        while (!Q.isEmpty()) {
            int v = Q.pollFirst();

            for (Node edge : edges[v]) {
                if (dist[edge.no] > dist[v] + edge.weight) {
                    dist[edge.no] = dist[v] + edge.weight;
                    if (edge.weight == 0)
                        Q.addFirst(edge.no);
                    else
                        Q.addLast(edge.no);
                }
            }
        }

        for (int i = 0; i < V; i++)
            System.out.println("Distance from the source node to " + i + ": " + dist[i]);
    }

    static void insertEdge(int u, int v, int wt) {
        edges[u].add(new Node(v, wt));
        edges[v].add(new Node(u, wt));
    }

    public static void main(String[] args) {
        for (int i = 0; i < V; i++)
            edges[i] = new ArrayList<>();

        insertEdge(0, 1, 0);
        insertEdge(0, 2, 1);
        insertEdge(1, 3, 1);
        insertEdge(3, 4, 0);
        insertEdge(4, 5, 1);
        insertEdge(5, 2, 1);

        int src = 0;
        zeroOneBFS(src);
    }
}

from collections import deque

V = 6
edges = [[] for _ in range(V)]

class Node:
    def __init__(self, no, weight):
        self.no = no
        self.weight = weight

def zero_one_bfs(src):
    dist = [float('inf')] * V
    dist[src] = 0

    Q = deque()
    Q.append(src)

    while Q:
        v = Q.popleft()

        for edge in edges[v]:
            if dist[edge.no] > dist[v] + edge.weight:
                dist[edge.no] = dist[v] + edge.weight
                if edge.weight == 0:
                    Q.appendleft(edge.no)
                else:
                    Q.append(edge.no)

    for i in range(V):
        print(f"Distance from the source node to {i}: {dist[i]}")

def insert_edge(u, v, wt):
    edges[u].append(Node(v, wt))
    edges[v].append(Node(u, wt))

if __name__ == "__main__":
    insert_edge(0, 1, 0)
    insert_edge(0, 2, 1)
    insert_edge(1, 3, 1)
    insert_edge(3, 4, 0)
    insert_edge(4, 5, 1)
    insert_edge(5, 2, 1)

    src = 0
    zero_one_bfs(src)

Why to use 0-1 BFS Algorithm?

The 0-1 BFS algorithm is utilized for its efficiency and versatility in solving shortest path problems in graphs with weighted edges of only 0 or 1. Here's why it's advantageous:

• Efficiency: 0-1 BFS has a time complexity of O(V + E), where V is the number of vertices and E is the number of edges, making it highly efficient compared to other shortest path algorithms like Dijkstra's algorithm.
• Optimality: In graphs where edges have weights restricted to 0 or 1, the 0-1 BFS algorithm always finds the shortest path from the source node to all other nodes, ensuring optimality in the shortest path solution.
• Space Complexity: The space complexity of 0-1 BFS is O(V), which is relatively low compared to other algorithms like Dijkstra's, which can have a higher space complexity due to priority queues or heaps.
• Simplicity: The algorithm is straightforward to implement and understand, requiring only a deque (double-ended queue) data structure for traversal.
• Applications: 0-1 BFS finds applications in various domains such as routing algorithms in computer networks, grid-based pathfinding in games and robotics, and solving shortest path problems in graphs with binary weights, making it a versatile tool in algorithmic problem-solving.

Frequently asked questions

Can we use Dijkstra for this problem? 

Yes, we can find the shortest path in a weighted graph using Dijkstra; it runs with time complexity of O(E + V log V). 

What is the BFS sequence?

The breadth-First Search (BFS) algorithm traverses the graph in a breadthward motion and uses a queue data structure to get the next vertex to start a search when a dead end occurs in any iteration.

What is the time complexity of the BFS algorithm?

The time complexity of the BFS algorithm is O(V+E) when the adjacency list is used as every node is visited once and O(V ²) when the adjacency matrix is used.

Conclusion

So, this article discussed the shortest path in an unweighted and weighted graph, using the 0-1 BFS algorithm with an example and its code in the C++ programming language.

If you are a beginner in coding and want to learn DSA, you can look for our guided path for DSA, which is free! 

In case of any comments or suggestions, feel free to post them in the comments section.