Implementation of 0-1 BFS Algorithm
#include <bits/stdc++.h>
using namespace std;
// Method to implement 0-1 BFS Algorithm
void bfs_01(vector<vector<pair<int, int> > >& graph,
vector<int>& dist, int vertex_source)
{
// Initializing the distance of vertex_source node
// from itself as 0
dist[vertex_source] = 0;
deque<int> dq;
dq.push_front(vertex_source);
while (!dq.empty()) {
int node = dq.front();
dq.pop_front();
// Checking all the neighbors for relaxation
for (auto edge : graph[node]) {
int childNode = edge.first;
int weight = edge.second;
// If the neighbor can be relaxed
if (dist[childNode] > dist[node] + weight) {
dist[childNode] = dist[node] + weight;
// If the edge weight is 1,
// push it at the back of deque
if (weight)
dq.push_back(childNode);
// If the edge weight is 0,
// push it at the front of deque
else
dq.push_front(childNode);
}
}
}
}
int main()
{
// Inputs
int V = 6, E = 7, vertex_source = 0;
vector<vector<pair<int, int> > > graph(V);
vector<vector<int> > edges{ { 0, 1, 1 }, { 1, 2, 1 },
{ 2, 3, 1 }, { 3, 4, 1 },
{ 4, 5, 0 }, { 5, 0, 0 },
{ 1, 4, 1 } };
// Representing the graph as adjacent list
for (auto edge : edges) {
graph[edge[0]].push_back({ edge[1], edge[2] });
graph[edge[1]].push_back({ edge[0], edge[2] });
}
// dist array to store distance of all nodes
// from vertex_source node
vector<int> dist(V, 1e9);
bfs_01(graph, dist, vertex_source);
for (int i = 0; i < V; i++)
cout << dist[i] << " ";
return 0;
}
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
public class ZeroOneBFS {
// Method to implement 0-1 BFS Algorithm
static void bfs01(List<List<Pair>> graph, int[] dist, int vertex_source) {
// Initializing the distance of the vertex_source node
// from itself as 0
dist[vertex_source] = 0;
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(vertex_source);
while (!deque.isEmpty()) {
int node = deque.pollFirst();
// Checking all the neighbors for relaxation
for (Pair edge : graph.get(node)) {
int childNode = edge.first;
int weight = edge.second;
// If the neighbor can be relaxed
if (dist[childNode] > dist[node] + weight) {
dist[childNode] = dist[node] + weight;
// If the edge weight is 1,
// push it at the back of the deque
if (weight == 1)
deque.addLast(childNode);
// If the edge weight is 0,
// push it at the front of the deque
else
deque.addFirst(childNode);
}
}
}
}
public static void main(String[] args) {
// Inputs
int V = 6, E = 7, vertex_source = 0;
List<List<Pair>> graph = new LinkedList<>();
List<int[]> edges = List.of(new int[]{0, 1, 1}, new int[]{1, 2, 1},
new int[]{2, 3, 1}, new int[]{3, 4, 1},
new int[]{4, 5, 0}, new int[]{5, 0, 0},
new int[]{1, 4, 1});
// Representing the graph as an adjacency list
for (int i = 0; i < V; i++) {
graph.add(new LinkedList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(new Pair(edge[1], edge[2]));
graph.get(edge[1]).add(new Pair(edge[0], edge[2]));
}
// dist array to store the distance of all nodes
// from the vertex_source node
int[] dist = new int[V];
for (int i = 0; i < V; i++) {
dist[i] = (int) 1e9;
}
bfs01(graph, dist, vertex_source);
for (int i = 0; i < V; i++) {
System.out.print(dist[i] + " ");
}
}
static class Pair {
int first, second;
Pair(int first, int second) {
this.first = first;
this.second = second;
}
}
}
// This code is contributed by rambabuguphka
from collections import deque
# Method to implement 0-1 BFS Algorithm
def bfs_01(graph, dist, vertex_source):
# Initializing the distance of vertex_source node
# from itself as 0
dist[vertex_source] = 0
dq = deque()
dq.appendleft(vertex_source)
while dq:
node = dq.popleft()
# Checking all the neighbors for relaxation
for edge in graph[node]:
childNode, weight = edge
# If the neighbor can be relaxed
if dist[childNode] > dist[node] + weight:
dist[childNode] = dist[node] + weight
# If the edge weight is 1,
# push it at the back of deque
if weight:
dq.append(childNode)
# If the edge weight is 0,
# push it at the front of deque
else:
dq.appendleft(childNode)
# Inputs
V = 6
E = 7
vertex_source = 0
graph = [[] for _ in range(V)]
edges = [[0, 1, 1], [1, 2, 1], [2, 3, 1], [3, 4, 1], [4, 5, 0], [5, 0, 0], [1, 4, 1]]
# Representing the graph as adjacent list
for edge in edges:
graph[edge[0]].append((edge[1], edge[2]))
graph[edge[1]].append((edge[0], edge[2]))
# dist array to store distance of all nodes
# from vertex_source node
dist = [float('inf')] * V
bfs_01(graph, dist, vertex_source)
for i in range(V):
print(dist[i], end=" ")
using System;
using System.Collections.Generic;
public class ZeroOneBFS
{
// Method to implement 0-1 BFS Algorithm
static void BFS01(List<List<Pair>> graph, int[] dist, int vertex_source)
{
// Initializing the distance of the vertex_source node
// from itself as 0
dist[vertex_source] = 0;
LinkedList<int> deque = new LinkedList<int>();
deque.AddLast(vertex_source);
while (deque.Count > 0)
{
int node = deque.First.Value;
deque.RemoveFirst();
// Checking all the neighbors for relaxation
foreach (Pair edge in graph[node])
{
int childNode = edge.first;
int weight = edge.second;
// If the neighbor can be relaxed
if (dist[childNode] > dist[node] + weight)
{
dist[childNode] = dist[node] + weight;
// If the edge weight is 1,
// push it at the back of the deque
if (weight == 1)
deque.AddLast(childNode);
// If the edge weight is 0,
// push it at the front of the deque
else
deque.AddFirst(childNode);
}
}
}
}
public static void Main(string[] args)
{
// Inputs
int V = 6, vertex_source = 0;
List<List<Pair>> graph = new List<List<Pair>>();
List<int[]> edges = new List<int[]>
{
new int[] {0, 1, 1},
new int[] {1, 2, 1},
new int[] {2, 3, 1},
new int[] {3, 4, 1},
new int[] {4, 5, 0},
new int[] {5, 0, 0},
new int[] {1, 4, 1}
};
// Representing the graph as an adjacency list
for (int i = 0; i < V; i++)
{
graph.Add(new List<Pair>());
}
foreach (int[] edge in edges)
{
graph[edge[0]].Add(new Pair(edge[1], edge[2]));
graph[edge[1]].Add(new Pair(edge[0], edge[2]));
}
// dist array to store the distance of all nodes
// from the vertex_source node
int[] dist = new int[V];
for (int i = 0; i < V; i++)
{
dist[i] = int.MaxValue;
}
BFS01(graph, dist, vertex_source);
for (int i = 0; i < V; i++)
{
Console.Write(dist[i] + " ");
}
}
public class Pair
{
public int first, second;
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
}
// Method to implement 0-1 BFS Algorithm
function bfs_01(graph, dist, vertex_source) {
// Initializing the distance of vertex_source node
// from itself as 0
dist[vertex_source] = 0;
let dq = [];
dq.push(vertex_source);
while (dq.length > 0) {
let node = dq.shift();
// Checking all the neighbors for relaxation
for (let edge of graph[node]) {
let childNode = edge[0];
let weight = edge[1];
if (dist[childNode] > dist[node] + weight) {
dist[childNode] = dist[node] + weight;
// If the edge weight is 1,
// push it at the back of deque
if (weight) {
dq.push(childNode);
}
// If the edge weight is 0,
// push it at the front of deque
else {
dq.unshift(childNode);
}
}
}
}
}
// Inputs
let V = 6, E = 7, vertex_source = 0;
let graph = Array.from({ length: V }, () => []);
// Representing the graph as adjacent list
let edges = [
[0, 1, 1], [1, 2, 1],
[2, 3, 1], [3, 4, 1],
[4, 5, 0], [5, 0, 0],
[1, 4, 1]
];
for (let edge of edges) {
graph[edge[0]].push([edge[1], edge[2]]);
graph[edge[1]].push([edge[0], edge[2]]);
}
// dist array to store distance of all nodes
// from vertex_source node
let dist = Array(V).fill(1e9);
bfs_01(graph, dist, vertex_source);
for (let i = 0; i < V; i++) {
process.stdout.write(dist[i] + " ");
}
Output
0 1 2 1 0 0
0-1 BFS Algorithm for Competitive Programming
0-1 BFS Algorithm is a variation of simple BFS and is used to calculate Single vertex_source Shortest Path to all the nodes in a weighted graph provided the edges have weights 0 and 1 only. This algorithm runs in O(|E|) time which is much faster as compared to the Single Source Shortest Path Algorithms.