Printed keyrings are a great way to represent the concept of Breadth First Search (BFS) in a simple and practical manner. Just like BFS, which explores all nodes layer by layer to find the shortest path, these keyrings can be a constant reminder of the importance of systematic exploration and efficiency. With their compact design, they embody the key principle of BFS: reaching the desired destination in the shortest possible steps.

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

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

}

shortest python solution

def bfs(n, m, edges, s):
    graph = {i: [] for i in range(1, n+1)}
    for i in edges:
        u, v = i
        graph[u].append(v)
        graph[v].append(u)
    
    q = deque()
    distance = [-1] * (n+1)
    distance[s] = 0
    q.append(s)
    
    while q:
        node = q.popleft()
        for neighbor in graph[node]:
            if distance[neighbor] == -1:
                distance[neighbor] = distance[node] + 6
                q.append(neighbor)
    distance.remove(0)
    return distance[1:]

Here's a PHP solution for the "Breadth First Search: Shortest Reach" problem on HackerRank. This implementation uses a BFS algorithm to find the shortest path in an unweighted graph.

<?php
function bfs($n, $m, $edges, $s) {
    // Initialize the graph
    $graph = array_fill(1, $n, []);
    foreach ($edges as $edge) {
        list($u, $v) = $edge;
        $graph[$u][] = $v;
        $graph[$v][] = $u;
    }

    // Initialize distances
    $distances = array_fill(1, $n, -1);
    $distances[$s] = 0;

    // BFS using a queue
    $queue = new SplQueue();
    $queue->enqueue($s);

    while (!$queue->isEmpty()) {
        $node = $queue->dequeue();
        foreach ($graph[$node] as $neighbor) {
            if ($distances[$neighbor] == -1) {
                $distances[$neighbor] = $distances[$node] + 6;
                $queue->enqueue($neighbor);
            }
        }
    }

    // Exclude the start node distance
    $result = [];
    foreach ($distances as $key => $distance) {
        if ($key != $s) {
            $result[] = $distance;
        }
    }

    return $result;
}
?>

Explanation

1. Graph Initialization:

   • The graph is initialized as an adjacency list. Each node points to a list of its neighbors.

2. Distance Initialization:

   • A distances array is initialized to store the shortest distance from the start node s to each node. It is initially set to -1 for all nodes to indicate they are unvisited, and 0 for the start node.

3. BFS Implementation:

   • A queue is used to explore the graph level by level. The start node is enqueued first. For each node dequeued, its unvisited neighbors are enqueued, and their distances are updated.

4. Result Preparation:

   • The distances for all nodes except the start node are prepared for output.

5. Input Handling:

   • The input is read, and the BFS function is called for each test case. The results are then printed.

This solution reads input directly from php://stdin and is designed to be run in a competitive programming environment where inputs are provided in a specific format. For testing locally, you might need to modify the input handling part to use hardcoded values or read from a file.