In normal BFS of a graph all edges have equal weight but in 0-1 BFS some edges may have 0 weight and some may have 1 weight.
For Example:
A vector, d will be defined to store distances between different vertices from source(s). d[s] will be 0 as the distance from source to source is 0. s will be pushed into the front of the deque(q). We’ll visit connected nodes and keep popping the previously pushed node at the front of the queue. We’ll assign u and w as first second edge respectively and push the edge connecting node having weight 0 to front of the queue and if the weight is 1, push it to the back of the queue, this will be repeated till the queue is empty which denotes all the nodes are visited.
Here is the basic code of the algorithm:
vector<int> d(n, INF);
d[s] = 0;
deque<int> q;
q.push_front(s);
while (!q.empty()) {
int v = q.front();
q.pop_front();
for (auto edge : adj[v]) {
int u = edge.first;
int w = edge.second;
if (d[v] + w < d[u]) {
d[u] = d[v] + w;
if (w == 1)
q.push_back(u);
else
q.push_front(u);
}
}
}
Let’s understand this algorithm with a pictorial representation of a graph.
Explanation:
The edge with weight 1 will be pushed to the back of the queue so notice nodes 2,5,4 and 3 was added at the back of the queue as evident from the graph and the rest with weight 0 will be pushed in front, the front will always be popped (removed) after being pushed off course and the back element moves to the front, but when in the 5th step 3 was popped and due to 3-4 linkage have weight 0 therefore pushed in front.
Time Complexity:
Suppose a graph G, has V vertices and E edges. It is a weighted graph with boolean weights i.e. either 0 or 1.
So while traversing the graph, while visiting a vertex we know we only have two possibilities, an edge having weight 0 or another edge having weight 1, we also know the queue holds two consecutive successive elements (nodes).
So if the edge weight equals 0 we will push the node to the front and if not push it back to the end, this allows our queue to remain sorted.
Thus all the nodes are visited minimum once the concluding time taken to visit all nodes equals sum of the number of edges and vertices. So, the time complexity of 0-1 BFS is O(E + V), which is linear and more efficient than
Dijkstra: O(V2+E) -> (O(E + V Log V)
Example of 0-1 BFS Algorithm
Suppose a graph with V nodes and E edges. Edges have binary weights (0 or 1). The source node is the 2nd node and we need to find the shortest path from the source node to every other node. Seems sound na. Our logic remains the same, jog your memory with me…We will use a double-ended queue (DEQUE) because it allows insertion and deletion at both ends which is exactly what we need:
- Traverse through all the nodes (first the source node will be pushed in front then its neighbour after popping source)
- Checking the weight of all the edges
- Pushing the nodes in the queue, if weight 0 then in front else back of the queue
- Printing the sum of the weight of edges making shortest path from source node to other nodes
We have 9 nodes in this graph, source is the 2nd node, there are 0 and 1 weights on the edges.
Here is the code for the 0-1 BFS in C++. The above graph is taken as input to the program :
#include<iostream>
#include<vector>
#include <bits/stdc++.h>
#include<deque>
//number of vertices
#define V 9
using namespace std;
//a structure to represent edges
struct node {
//no denotes the node(vertex) and weight denotes the weight of the edge
int no, weight;
};
//defining a vector of type node to store edges
vector <node> graphEdges[V];
//prints shortest distance from given source to every other node(vertex)
void display0OneBFS(int src) {
//initializing distances from source
int dist[V];
for (int i=0; i<V; i++)
dist[i] = INT_MAX;
deque <int> Q; //defining double ended queue
dist[src] = 0; //distance from source to source is 0
Q.push_back(src); //pushing source into deque
//while deque has some element inside and not empty, condition holds TRUE
while (!Q.empty()) {
int v = Q.front(); //storing front of queue in variable v
Q.pop_front(); //popping out front element from deque
for (int i=0; i<graphEdges[v].size(); i++) {
//checking for ideal distance
if (dist[graphEdges[v][i].no] > dist[v] + graphEdges[v][i].weight) {
dist[graphEdges[v][i].no] = dist[v] + graphEdges[v][i].weight;
if (graphEdges[v][i].weight == 0) //if 0 weight edge, store at front of deque
Q.push_front(graphEdges[v][i].no);
else
Q.push_back(graphEdges[v][i].no); //else if 1 weight edge, store at back of deque
}
//vertices will be processed in a sorted increasing weight order
}
}
//printing the distance from source node with minimum weight i.e. shortest path in 0-1 weighted graph
for (int i=0; i<V; i++)
cout<<"Distance from source node to "<<i<<":"<<"\t"<<dist[i]<<endl;
}
//inserting edges with their respective weights
void insertEdge(int u, int v, int wt) {
graphEdges[u].push_back({v, wt});
graphEdges[v].push_back({u, wt});
}
int main() {
insertEdge(0, 1, 1); //1 on the right most represents weight of the edge; 0,1 are edges from 0 to 1 and so on
insertEdge(0, 2, 1);
insertEdge(0, 7, 1);
insertEdge(0, 8, 0);
insertEdge(1, 2, 0);
insertEdge(1, 3, 1);
insertEdge(1, 7, 0);
insertEdge(2, 5, 1);
insertEdge(2, 6, 0);
insertEdge(3, 4, 1);
insertEdge(4, 5, 1);
insertEdge(5, 6, 1);
insertEdge(6, 7, 1);
insertEdge(7, 8, 1);
int src = 2;
display0OneBFS(src);
}
Output:
Distance from source node to 0: 1
Distance from source node to 1: 0
Distance from source node to 2: 0
Distance from source node to 3: 1
Distance from source node to 4: 2
Distance from source node to 5: 1
Distance from source node to 6: 0
Distance from source node to 7: 0
Distance from source node to 8: 1
Practice this into a compiler and try manipulating the values if you understand the flow of code, make a graph yourself with pen paper and give edges 0 and 1 weight randomly, put the values in this code, run it, and match it.
Implementation of 0-1 BFS on Java and Python3
You can find the implementation of the above graph problem in Java and Python here:
Java Program
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
public class display0OneBFS{
//class to represent edges
private static class Node {
//no denotes the node(vertex) and weight denotes the weight of the edge
int no;
int weight;
public Node(int no, int wt) {
this.no = no;
this.weight = wt;
}
}
private static final int numVertex = 9; //number of vertices
//defining an arraylist of type node to store edges
private ArrayList<Node>[] edges = new ArrayList[numVertex];
public display0OneBFS() {
for (int i = 0; i < edges.length; i++) {
edges[i] = new ArrayList<Node>();
}
}
//inserting edges with their respective weights
public void insertEdge(int u, int v, int wt) {
edges[u].add(edges[u].size(), new Node(v, wt));
edges[v].add(edges[v].size(), new Node(u, wt));
}
//prints shortest distance from given source to every other node(vertex) public void display0OneBFS(int src) {
// initialize distances from source
int[] dist = new int[numVertex];
for (int i = 0; i < numVertex; i++) {
dist[i] = Integer.MAX_VALUE;
}
//defining double ended queue
Deque<Integer> queue = new ArrayDeque<Integer>();
//distance from source to source is 0
dist[src] = 0;
//pushing source into deque
queue.addLast(src);
//while deque has some element inside and not empty, condition holds TRUE
while (!queue.isEmpty()) {
int v = queue.removeFirst();
for (int i = 0; i < edges[v].size(); i++) {
// checking for ideal distance
if (dist[edges[v].get(i).no] >
dist[v] + edges[v].get(i).weight) {
// update the distance
dist[edges[v].get(i).no] =
dist[v] + edges[v].get(i).weight;
//if 0 weight edge, store at front of deque
//else if 1 weight edge, store at back of deque
//so that vertices will be processed in a sorted increasing weight order
if (edges[v].get(i).weight == 0) {
queue.addFirst(edges[v].get(i).no);
} else {
queue.addLast(edges[v].get(i).no);
}
}
}
}
//printing the distance from source node with minimum weight i.e. shortest path in 0-1 weighted graph
for (int i = 0; i < dist.length; i++) {
System.out.print(dist[i] + " ");
}
}
public static void main(String[] args) {
display0OneBFS graph = new display0OneBFS();
//1 on the right most represents weight of the edge; 0,1 are edges from 0 to 1 and so on
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(0, 7, 1);
graph.insertEdge(0, 8, 0);
graph.insertEdge(1, 2, 0);
graph.insertEdge(1, 3, 1);
graph.insertEdge(1, 7, 0);
graph.insertEdge(2, 5, 1);
graph.insertEdge(2, 6, 0);
graph.insertEdge(3, 4, 1);
graph.insertEdge(4, 5, 1);
graph.insertEdge(5, 6, 1);
graph.insertEdge(6, 7, 1);
graph.insertEdge(7, 8, 1);
int src = 2;//source node
graph.display0OneBFS(src);
return;
}
}
Python Program
from sys import maxsize as INT_MAX
from collections import deque
# no.of vertices
V = 9
# a structure to represent edges
class node:
def __init__(self, no, weight):
# two variable, no denote the node
# and other the weight
self.no = no
self.weight = weight
# vector to store edges
edges = [0] * V
for i in range(V):
edges[i] = []
# Prints shortest distance from
# given source to every other node
def graph.display0OneBFS(src: int):
# Initialize distances from source
dist = [0] * V
for i in range(V):
dist[i] = INT_MAX
# defining double ended queue
Q = deque()
# distance from source to source is 0
dist[src] = 0
# adding source into deque
Q.append(src)
while Q:
v = Q[0]
Q.popleft()
for i in range(len(edges[v])):
# checking for the ideal distance
if (dist[edges[v][i].no] >
dist[v] + edges[v][i].weight):
dist[edges[v][i].no] = dist[v] + edges[v][i].weight
# if 0 weight edge, store at front of deque
# else if 1 weight edge, store at back of deque
# so that vertices will be processed in a sorted increasing weight order
if edges[v][i].weight == 0:
Q.appendleft(edges[v][i].no)
else:
Q.append(edges[v][i].no)
# printing the distance from source node with minimum weight i.e. shortest path in 0-1 weighted graph
for i in range(V):
print(dist[i], end = " ")
print()
def insertEdge(u: int, v: int, wt: int):
edges[u].append(node(v, wt))
edges[u].append(node(v, wt))
# Driver Code
if __name__ == "__main__":
# 1 on the right most represents weight of the edge; 0,1 are edges from 0 to 1 and so on
insertEdge(0, 1, 1);
insertEdge(0, 2, 1);
insertEdge(0, 7, 1);
insertEdge(0, 8, 0);
insertEdge(1, 2, 0);
insertEdge(1, 3, 1);
insertEdge(1, 7, 0);
insertEdge(2, 5, 1);
insertEdge(2, 6, 0);
insertEdge(3, 4, 1);
insertEdge(4, 5, 1);
insertEdge(5, 6, 1);
insertEdge(6, 7, 1);
insertEdge(7, 8, 1);
# source node
src = 2
display0OneBFS(src)
Conclusion
Let’s gather what we have learned here, we started with BFS as one of the most common graph traversal algorithms where we start traversing from the starting or source node and continue visiting the graph by travelling to neighbour nodes (nodes directly connected to source node) thus exploring all the nodes then we must visit the nodes of next layer i.e. nodes connected to the neighbouring nodes of source. We use a boolean array for BFS.
Now for a graph having 0 and 1 weights we saw a special variation of BFS called 0-1 BFS which uses a double ended queue to find the shortest path from a given source node to every other node.
It is a special variation because of its time complexity→ O(V+E) i.e. big O of sum of number of vertices and edges to find the minimum distance as the nodes are stored in sorted order, as per their distance from the source node.
For instance, if you are on a node at distance d from source you will only have a choice of 0 or 1 weight so any neighbor node added in the deque could be at maximum d+1 distance. So adding node having 0 weighted edge at the front and 1 weighted at back keeps the queue sorted.
