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.