In this HackerRank Breadth-First Search: Shortest Reach problem solution Consider an undirected graph where each edge weighs 6 units. Each of the nodes is labeled consecutively from 1 to n.
You will be given a number of queries. For each query, you will be given a list of edges describing an undirected graph. After you create a representation of the graph, you must determine and report the shortest distance to each of the other nodes from a given starting position using the breadth-first search algorithm (BFS). Return an array of distances from the start node in node number order. If a node is unreachable, return -1 for that node.
Problem solution in Python.
def bfs_paths(graph, start, goal):
queue = [(start,[start])]
while queue:
v, path = queue.pop(0)
for next in graph[v] - set(path):
if next == goal:
yield path + [next]
else:
queue.append((next, path + [next]))
def shortest_path(graph, start, goal):
if len(graph[start])==0 or len(graph[goal])==0:
return -1
try:
return 6*(len(next(bfs_paths(graph, start, goal)))-1)
except StopIteration:
return -1
t = int(input())
for tt in range(t):
ret = []
n,m = map(int, input().split())
graph = dict((i,set()) for i in range(1,n+1))
for mm in range(m):
s,d = map(int, input().split())
graph[s].add(d)
graph[d].add(s)
start = int(input())
for a in list(x for x in range(1,n+1) if x != start):
ret.append(shortest_path(graph, start, a))
print(' '.join(map(str, ret)))Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
static void bfs(Vector<Vector<Integer>> g, int s) {
int n = g.size();
int[] dist = new int[g.size()];
for (int i = 0; i < n; i++) {
dist[i] = n;
}
dist[s] = 0;
boolean[] used = new boolean[g.size()];
Arrays.fill(used, false);
Vector<Integer> queue = new Vector<>();
queue.add(s);
used[s] = true;
for (int i = 0; i < queue.size(); i++) {
queue.get(i);
int v = queue.get(i);
for (int u : g.get(v)) {
if (!used[u]) {
used[u] = true;
dist[u] = dist[v] + 1;
queue.add(u);
}
}
}
for (int i = 0; i < dist.length; i++) {
if (dist[i] != 0) {
if (dist[i] == n) {
System.out.print(-1 + " ");
} else {
System.out.print((dist[i] * 6) + " ");
}
}
}
}
public static void main(String[] args) {
Vector<Vector<Integer>> g = new Vector<Vector<Integer>>();
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for (int i = 0; i < t; i++) {
int n = in.nextInt();
for (int c = 0; c < n; c++) {
g.add(new Vector<>());
}
int m = in.nextInt();
for (int k = 0; k < m; k++) {
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;
g.get(a).add(b);
g.get(b).add(a);
}
int s = in.nextInt() - 1;
bfs(g,s);
g.clear();
System.out.println();
}
}
}Problem solution in C++.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include<limits>
using namespace std;
struct entity
{
int node;
int weight;
};
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T, N , M, from, to, s;
entity e, e1;
cin >> T;
for(int i= 0; i < T; i++)
{
cin >> N >> M;
vector<vector<int>> aList(N);
vector<int> output(N,numeric_limits<int>::max());
vector<int> finished(N, -1);
vector<int>::iterator it;
for(int i = 0 ; i < M; i++)
{
cin >> from >> to;
it = find (aList[from-1].begin(), aList[from-1].end(), to -1);
if (it == aList[from-1].end())
{
aList[from-1].push_back(to - 1);
aList[to-1].push_back(from - 1);
}
}
cin >> s;
output[s-1] = 0;
// cout << s << endl;
queue<entity> myqueue;
/* for(int i = 0 ; i < N; i++)
{
cout << i << "\t";
for(int j = 0; j < aList[i].size(); j++)
{
cout << aList[i][j] << " ";
}
cout << endl;
}*/
for(int v : aList[s-1])
{
// cout << v;
e.node = v;
e.weight = 6;
myqueue.push(e);
}
finished[s-1] = 1;
while (!myqueue.empty())
{
e = myqueue.front();
//cout << e.node << " " << e.weight << endl;
if (e.weight < output[e.node])
{
output[e.node] = e.weight;
}
finished[e.node] = 1;
myqueue.pop();
for(int v: aList[e.node])
{
if(finished[v] != 1)
{
e1.node = v;
e1.weight = 6 + e.weight;
myqueue.push(e1);
}
}
}
for( int i = 0 ; i < output.size() ; i++)
{
if(i!= s-1)
{
if( output[i]!= numeric_limits<int>::max())
cout << output[i] << " ";
else
cout << -1 << " ";
}
}
cout << endl;
}
return 0;
}
Problem solution in C.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void solve();
void BFS(int, int a[][1000], int);
typedef struct LLNode{
struct LLNode *next;
int val;
}Node;
typedef struct Queue{
Node *head;
Node *tail;
int length;
}que,queue;
int enqueue(que *q, int val);
int dequeue(que *q);
int isEmpty(que *q);
/*
* RETURN
* -1 -> failed to enqueue
* 0 -> successfully enqueued
*/
int enqueue(que *q, int val){
Node *newNode = (Node *)malloc(sizeof(Node));
if(!newNode)
return -1;
newNode->next = NULL;
newNode->val= val;
if(isEmpty(q)){
q->head = newNode;
q->tail = newNode;
q->length++;
} else {
q->tail->next = newNode;
q->tail = newNode;
q->length++;
}
return 0;
}
int dequeue(que *q){
if(isEmpty(q))
return -1;
int ret = q->head->val;
Node *tmp = q->head;
q->head = q->head->next;
free(tmp);
q->length--;
return ret;
}
int isEmpty(que *q){
if(q->head == NULL)
return 1;
else
return 0;
}
void BFS(int st, int adj[][1000],int len){
int i;
que *q = (que *)malloc(sizeof(q));
q->head = NULL;
q->length = 0;
q->tail = NULL;
enqueue(q,st);
int *dist = (int *)malloc(sizeof(int)*len);
for(i=0;i<len;i++)
dist[i] = -1;
dist[st] = 0;
while(!isEmpty(q)){
int v = dequeue(q);
for(i=0;i<len;i++){
if(adj[v][i] == 1 || adj[i][v] == 1){
if(dist[i] != -1 && dist[v] + 6 < dist[i]){
dist[i] = dist[v] + 6;
enqueue(q,i);
}
else if(dist[i] == -1){
dist[i] = dist[v] + 6;
enqueue(q,i);
}
}
}
}
for(i=0;i<len;i++){
if(i != st){
printf("%d ",dist[i]);
}
}
free(dist);
free(q);
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int i,T = 0;
scanf("%d",&T);
for(i = 0; i<T;i++){
int st,i,N,M,x,y;
scanf("%d",&N);
scanf("%d",&M);
int adj[1000][1000] = {0};// = (int **)calloc(N*N,(sizeof(int)));
for(i=0;i<M;i++){
scanf("%d",&x);
scanf("%d",&y);
adj[x-1][y-1] = 1;
}
scanf("%d",&st);
BFS(st-1,adj,N);
printf("\n");
}
return 0;
}
0 Comments