BFS: Shortest Reach in a Graph


Problem Statement :


Consider an undirected graph consisting of n nodes where each node is labeled from 1 to n  and the edge between any two nodes is always of length 6. We define node s to be the starting position for a BFS. Given a graph, determine the distances from the start node to each of its descendants and return the list in node number order, ascending. If a node is disconnected, it's distance should be -1.

For example, there are  n = 6 nodes in the graph with a starting node s = 1 . The list of edges = [ [1,2], [2, 3],[3, 4 ], [1, 5 ] ] and each has a weight of 6 .


Function Description

Define a Graph class with the required methods to return a list of distances.

Input Format

The first line contains an integer, q, the number of queries.

Each of the following q sets of lines is as follows:

The first line contains two space-separated integers, n and m, the number of nodes and the number of edges.
Each of the next m lines contains two space-separated integers, u and v, describing an edge connecting node u to node v.
The last line contains a single integer, s, the index of the starting node.

Output Format

For each of the q queries, print a single line of n - 1 space-separated integers denoting the shortest distances to each of the n - 1 other nodes from starting position s. These distances should be listed sequentially by node number (i.e.1, 2 , . . . , n ), but should not include node s. If some node is unreachable from s , print -1 as the distance to that node.

Sample Input

2
4 2
1 2
1 3
1
3 1
2 3
2


Sample Output

6 6 -1
-1 6


Solution :



title-img 


                            Solution in C :

In   C :




#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int addqueue(int t, int q[],int v);

int main()
{
    int q;
    scanf("%d",&q);
    
    while(q--)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        int a[n+1][n+1];
        
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
            {
                a[i][j]=-1;
            }
        }
        
        while(m--)
        {
            int u,v;
            scanf("%d %d",&u,&v);
            a[u][v]=6;
            a[v][u]=6;
        }
        int s;
        scanf("%d",&s);
        
        int ans[n+1];
        ans[0]=0;
        ans[s]=0;
        for(int i=1;i<=n;i++)
        {
            if(i!=s)
                ans[i]=-1;
        }
        
        int queue[n];
        queue[0]=s;
        int c=0,top=1;
        while(c!=top)
        {   
            
             for(int i=1;i<=n;i++)
             {
                if(a[queue[c]][i]==6)
                {
                    if(addqueue(top,queue,i))
                    {   
                        queue[top]=i;
                        top++;
                      //  ans[i]=6*(c+1);
                        ans[i]=6+ans[queue[c]];
                    }
                    
                }
             }
            c++;
        }
        for(int i=1;i<=n;i++)
        {
            if(i==s)
                continue;
            else
                printf("%d ",ans[i]);
        } printf("\n");
              
    }    
    return 0;
}

int addqueue(int t, int q[],int v)
{
    for(int i=0;i<t;i++)
    {
        if(q[i]==v)
            return 0;
    }
    return 1;
}
                        


                        Solution in C++ :

In  C++ :





#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
#include <queue>
using namespace std;

class Graph {
    public:
        Graph(int n) {
            data.resize(n);
        }
    
        void add_edge(int u, int v) {
            data[u].push_back(v);
            data[v].push_back(u);
        }
    
        vector<int> shortest_reach(int start) {
            vector<int> result(data.size(), -1);
            std::queue<int> q;
            q.push(start);
            result[start] = 0;
            while(!q.empty())
            {
                int v = q.front();
                q.pop();
                for(auto it = data[v].begin(); it != data[v].end(); it++)
                {
                    if (result[*it] < 0)
                    {
                        result[*it] = result[v]+6;
                        q.push(*it);
                    }
                }
            }
            //for(int i(start); i < data.size()-1; i++)
            //    result[i] = result[i+1];
            //result.resize(data.size()-1);
            return result;
        }
    
    private:
        std::vector<std::list<int> > data;
};

int main() {
    int queries;
    cin >> queries;
        
    for (int t = 0; t < queries; t++) {
      
      int n, m;
        cin >> n;
        // Create a graph of size n where each edge weight is 6: 
        Graph graph(n);
        cin >> m;
        // read and set edges
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            // add each edge to the graph
            graph.add_edge(u, v);
        }
      int startId;
        cin >> startId;
        startId--;
        // Find shortest reach from node s
        vector<int> distances = graph.shortest_reach(startId);

        for (int i = 0; i < distances.size(); i++) {
            if (i != startId) {
                cout << distances[i] << " ";
            }
        }
        cout << endl;
    }
    
    return 0;
}
                    


                        Solution in Java :

In  Java :




import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static class Graph {
        private int V;
        private LinkedList<Integer> [] G;
        
        public Graph(int size) {
            this.V = size;
            this.G = new LinkedList[V];
            
            for(int v = 0; v < V; v++)
                G[v] = new LinkedList<>();
        }

        public void addEdge(int first, int second) {
            G[first].add(second);
            G[second].add(first);
        }
        
        public int[] shortestReach(int startId) { // 0 indexed
            boolean [] visited = new boolean[V];
            Queue<Integer> q = new LinkedList<>();
            q.add(startId);
            visited[startId] = true;
            int size = 1;
            int distance = 6;
            int [] distTo = new int[V];
            Arrays.fill(distTo, -1);
            while(!q.isEmpty()) {
                int v = q.poll();
                for(int w : G[v]) {
                    if(!visited[w]) {
                        visited[w] = true;
                        distTo[w] = distance;
                        q.add(w);
                    }
                }
                
                if(--size == 0) {
                    size = q.size();
                    distance+=6;
                }
            }
            return distTo;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
      
        int queries = scanner.nextInt();
        
        for (int t = 0; t < queries; t++) {
            
            // Create a graph of size n where each edge weight is 6:
            Graph graph = new Graph(scanner.nextInt());
            int m = scanner.nextInt();
            
            // read and set edges
            for (int i = 0; i < m; i++) {
                int u = scanner.nextInt() - 1;
                int v = scanner.nextInt() - 1;
                
                // add each edge to the graph
                graph.addEdge(u, v);
            }
            
            // Find shortest reach from node s
            int startId = scanner.nextInt() - 1;
            int[] distances = graph.shortestReach(startId);
 
            for (int i = 0; i < distances.length; i++) {
                if (i != startId) {
                    System.out.print(distances[i]);
                    System.out.print(" ");
                }
            }
            System.out.println();            
        }
        
        scanner.close();
    }
}
                    


                        Solution in Python : 
                            
In   Python3 :





def find_all_dists(g, s):
    r = {}
    ss = {}
    for n in g[s]:
        r[n] = 1
        ss[n] = 1
    arr = [r]
    ss[s] = 0
    
    while True:
        r = {}
        pr = arr[-1]
        for key, c in pr.items():
            for ne in g[key]:
                if ne not in ss or ss[ne] > c+1:
                    if ne in r and r[ne] <= c+1:
                        continue
                    r[ne] = c+1
                    ss[ne] = c+1
        if r == {}:
            break
        arr.append(r)
    return ss

t = int(input())
for i in range(t):
    n,m = [int(value) for value in input().split()]
    graph = {}
    for i in range(n+1):
        graph[i+1] = []
    for i in range(m):
        u,v = [int(x) for x in input().split()]
        graph[u].append(v)
        graph[v].append(u)
        
    s = int(input())
    ss = find_all_dists(graph, s)
    #print(ss)
    res = []
    for i in range(1,n+1):
        if i == s:
            continue
        if i not in ss:
            res.append('-1')
        else:
            res.append(str(ss[i] * 6))
    print(" ".join(res))


View More Similar Problems

Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v

View Solution →

Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

View Solution →

Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

View Solution →

Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

View Solution →

Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

View Solution →

Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr

View Solution →