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; }