We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
public static List bfs(int n, int m, List> edges, int s)
{
//Initializing graph
var edgeWeight = 6;
var graph = new Dictionary>();
for (int i = 1; i <= n; i++)
graph[i] = new List();
//Filling graph
foreach(var edge in edges)
{
var node1 = edge[0];
var node2 = edge[1];
graph[node1].Add(node2);
graph[node2].Add(node1);
}
//Initializing distances
var queue = new Queue<int>();
var distance = new int[n + 1];
for (int i = 1; i <= n; i++)
distance[i] = -1;
distance[s] = 0;
queue.Enqueue(s);
//BFS
while(queue.Any())
{
var node = queue.Dequeue();
foreach(var neighbor in graph[node])
{
if (distance[neighbor] == -1)
{
distance[neighbor] = distance[node] + edgeWeight;
queue.Enqueue(neighbor);
}
}
}
//Filling result distances
var result = new List<int>();
for (int i = 1; i <= n; i++)
{
if (i == s)
continue;
result.Add(distance[i]);
}
return result;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Breadth First Search: Shortest Reach
You are viewing a single comment's thread. Return to all comments →
C# solution
public static List bfs(int n, int m, List> edges, int s) { //Initializing graph var edgeWeight = 6; var graph = new Dictionary>(); for (int i = 1; i <= n; i++) graph[i] = new List();
}