In this HackerRank BFS: Shortest Reach in a Graph Interview preparation kit problem there is 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, its distance should be -1.
Problem solution in Python programming.
t = int(input().strip()) def calculate_cost(nodes, travel_edges): new_edges = [] weight = 6 current_cost = 0 while travel_edges: for e in travel_edges: id, cost, edges = nodes[e-1] if cost == -1: new_edges = new_edges + edges cost = current_cost nodes[e-1] = (id, cost, edges) travel_edges = new_edges new_edges = [] current_cost += weight return nodes for test in range(t): n, m = [int(i) for i in input().strip().split()] nodes = [(i, -1, []) for i in range(1, n+1)] for edge in range(m): start, end = [int(i) for i in input().strip().split()] id, cost, edges = nodes[start-1] nodes[start-1] = (id, cost, edges + [end]) id, cost, edges = nodes[end-1] nodes[end-1] = (id, cost, edges + [start]) s = int(input().strip()) nodes = calculate_cost(nodes, [s]) weights = ' '.join([str(node[1]) for node in nodes if node[1] != 0]) print(weights)
Problem solution in Java Programming.
import java.util.*; class GraphNode{ int sumNodes; ArrayList<LinkedList<Integer>> adjList; public GraphNode(int numNodes){ this.sumNodes = numNodes; adjList = new ArrayList<LinkedList<Integer>>(); for(int i = 0; i < numNodes; i++){ adjList.add(new LinkedList<Integer>()); } } public void addEdge(int a, int b){ adjList.get(a).add(b); adjList.get(b).add(a); } } public class Solution { public static void getDistance(ArrayList<LinkedList<Integer>> adjList, int[] results, int s){ LinkedList<Integer> q = new LinkedList(); boolean[] isVisited = new boolean[adjList.size()]; q.add(s); isVisited[s] = true; int count = 0; while(!q.isEmpty()){ int qSize = q.size(); for(int i = 0; i < qSize; i++){ int removed = q.poll(); results[removed] = count; for(int x: adjList.get(removed)){ if(!isVisited[x]){ q.add(x); isVisited[x] = true; } } } count += 6; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int q = sc.nextInt(); for(int i = 1; i <= q; i++){ int n = sc.nextInt(); int m = sc.nextInt(); GraphNode g = new GraphNode(n); for(int j = 1; j <= m; j++){ int a = sc.nextInt(); int b = sc.nextInt(); g.addEdge(a-1, b-1); } int s = sc.nextInt(); int[] results = new int[n]; Arrays.fill(results, -1); getDistance(g.adjList, results, s-1); for(int k = 0; k < n; k++){ if(k != s-1) System.out.print(results[k]+ " "); } System.out.println(); } } }
Problem solution in C++ programming.
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <queue> using namespace std; #define INF 1<<30 class Graph { public: vector<vector<int> > adj; int V; Graph(int n) { adj = vector<vector<int> >(n , vector<int>()); V = n; } void add_edge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } vector<int> shortest_reach(int start) { vector<int> dist( V , INF ); vector<bool> seen( V , false); queue<int> Q; dist[start] = 0; Q.push(start); seen[ start ] = true; while( !Q.empty() ){ int current = Q.front(); Q.pop(); for( int i = 0 ; i < adj[current].size() ; ++i ){ int neighbour = adj[current][i]; if( !seen[neighbour] && dist[ neighbour ] > dist[ current ] + 1 ){ dist[ neighbour ] = dist[ current ] + 1; Q.push( neighbour ); seen[ neighbour ] = true; } } } for( int i = 0 ; i < V ; ++i ){ if( i != start ){ if( dist[i] == INF ) dist[i] = -1; else dist[i] *= 6; } } return dist; } }; 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; }
Problem solution in C programming.
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> typedef struct node { int data; struct node * next; }node; typedef struct list { node * head; }list; void Insert(list *A,int src,int des) { node * temp = malloc(sizeof(node)); temp -> data = des; temp -> next = A[src].head; A[src].head = temp; } void BFS(list *A,int src,int n) { node * temp; int i,u,level[n],queue[n]; int front = 0, rear = 0; for(i=0;i<n;i++) level[i] = -1; queue[front++] = src; level[src] = 0; while(front>rear) { u = queue[rear++]; temp = A[u].head; while(temp != NULL) { if(level[temp->data]==-1) { queue[front++] = temp->data; level[temp->data] = level[u] + 6; } temp = temp->next; } } for(i=0;i<n;i++) { if(i!=src) printf("%d ",level[i]); } printf("n"); } int main() { int i,j,q,n,m,u,v,s; list A[1000]; scanf("%d",&q); for(i=0;i<q;i++) { scanf("%d%d",&n,&m); for(j=0;j<n;j++) A[j].head = NULL; for(j=0;j<m;j++) { scanf("%d%d",&u,&v); Insert(A,u-1,v-1); Insert(A,v-1,u-1); } scanf("%d",&s); BFS(A,s-1,n); } return 0; }
Problem solution in JavaScript programming.
var shortest = function(v, edges, start) { //console.log('v', v, 'edges', edges, 'start', start); var adj = {}; //Initialize distance array to -1 var dist = []; for (var i = 1; i <= v; i++) { dist[i] = -1; } dist[start] = 0; for (var i = 0; i < edges.length; i++) { var e1 = edges[i][0]; var e2 = edges[i][1]; adj[e1] = adj[e1] || []; adj[e1].push(e2); adj[e2] = adj[e2] || []; adj[e2].push(e1); } var queue = [start]; while (queue.length > 0) { var n = queue.shift(); var currentDist = dist[n]; var neighbors = adj[n] || []; neighbors.forEach(function(neighbor) { if (dist[neighbor] === -1) { dist[neighbor] = currentDist + 6; queue.push(neighbor); } }); } //filtering is fun, it skips over index 0 on its own because no value var res = dist.filter(function(f, index) { return index !== start; }); console.log(res.join(' ')); } var currentLine = 0; function readLine(input) { return input[currentLine++]; } function processData(input) { //Enter your code here var data = input.split('n'); var queries = parseInt(readLine(data)); for (var i = 0; i < queries; i++) { //console.log('data',data); var a = readLine(data); //console.log('a', a); var a0 = a.split(' '); var vertCount = parseInt(a0[0]); var edgeCount = parseInt(a0[1]); var edges = []; for (var j = 0; j < edgeCount; j++) { var edge = readLine(data).split(' '); edges.push([parseInt(edge[0]), parseInt(edge[1])]); } var start = parseInt(readLine(data)); shortest(vertCount, edges, start); } } process.stdin.resume(); process.stdin.setEncoding("ascii"); _input = ""; process.stdin.on("data", function (input) { _input += input; }); process.stdin.on("end", function () { processData(_input); });