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