0-1 BFS

Implement 0-1 BFS, where all edges weights are either 1 or 0.

Example:

Input:  n=5 , edges={{1,2,1},{1,3,0},{2,4,0},{3,4,1},{2,5,1},{4,5,1}}
Output: dist={0,1,0,1,2}

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class BFS01 {
    public static void main(String[] args) {
        // Adjacency Lists
        ArrayList<HashMap<Integer, Integer>> adj = new ArrayList<HashMap<Integer, Integer>>();
        int n = 6;
        // initialization of adj
        for (int i = 0; i < n; i++)
            adj.add(new HashMap<>());

        // make the graph {edge u--v with weight w}
        addEdge(adj, 1, 2, 1);
        addEdge(adj, 1, 3, 0);
        addEdge(adj, 2, 4, 0);
        addEdge(adj, 3, 4, 1);
        addEdge(adj, 4, 5, 1);
        addEdge(adj, 2, 5, 1);

        int dist[] = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);

        int source = 1;
        BFS(adj, n, source, dist);
        int a[]=Arrays.copyOfRange(dist, 1, dist.length);
        System.out.println(Arrays.toString(a));
    }

    // function for 0-1 BFS
    static void BFS(ArrayList<HashMap<Integer, Integer>> adj, int n, 
                int source, int[] dist) {

        // dist of source as 1
        dist[source] = 0;

        // take a deque
        Queue<Integer> q = new LinkedList<Integer>();

        // push the source at front
        // of queue
        q.add(source);

        // iterate till the queue is not
        // empty
        while (!q.isEmpty()) {
            // pop the front element from
            // queue

            int v = q.poll();

            // iterate for all adjacent nodes of
            // the current node
            HashMap<Integer, Integer> map = adj.get(v);
            for (Integer edge : map.keySet()) {
                {
                    int u = edge;
                    int w = map.get(edge);

                    // update weight for
                    // the new node
                    if (dist[v] + w < dist[u]) {
                        dist[u] = dist[v] + w;

                        // if weight is 1 then push
                        // it at back of queue
                        if (w == 1)
                            q.add(u);

                        // else push it at front of
                        // queue
                        else
                            q.add(u);

                    }
                }
            }
        }
    }

    private static void addEdge(ArrayList<HashMap<Integer, Integer>> adj, 
                    int u, int v, int w) {
        // undirected graph with weight
        adj.get(u).put(v, w);
        adj.get(v).put(u, w);
    }
}

C++

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

vector<pair<int,int>> arr[101];

//function to add edges into
//the graph
void addEdge(int u,int v,int w)
{
    arr[u].push_back({v,w});
    arr[v].push_back({u,w});
}

//function for 0-1 BFS
void BFS(int n,int source,vector<int> &dist)
{

  //dist of source as 1
   dist[source]=0;

   //take a deque
   deque<int> q;

   //push the source at front
   //of queue
   q.push_front(source);

   //iterate till the queue is not
   //empty
   while(!q.empty())
     {
         int v=q.front();

         //pop the front element from
         //queue
         q.pop_front();

         //iterate for all adjacent nodes of
         //the current node
         for(auto edge:arr[v])
           {
               int u=edge.first;
               int w=edge.second;

               //update  weight for
               //the new node
               if(dist[v]+w<dist[u])
                 {
                     dist[u]=dist[v]+w;

                     //if weight is 1 then push
                     //it at back of queue
                     if(w==1)
                       q.push_back(u);

                    //else push it at front of
                    //queue
                      else
                       q.push_front(u);
                      
                 }
           }
     }
}
int main()
{
    int n=5;
    addEdge(1,2,1);
    addEdge(1,3,0);
    addEdge(2,4,0);
    addEdge(3,4,1);
    addEdge(4,5,1);
    addEdge(2,5,1);

    vector<int> dist(n+1,INT_MAX);
    int source=1;
    BFS(n,source,dist);
    for(int i=1;i<=n;i++)
      cout<<dist[i]<<" ";
    return 0;
}