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.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Breadth First Search: Shortest Reach
  5. Discussions

Breadth First Search: Shortest Reach

Sort by

recency

|

695 Discussions

|

  • CS_2212256_T
     + 0 comments
    class Result {

    /*
     * Complete the 'bfs' function below.
     *
     * The function is expected to return an INTEGER_ARRAY.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. INTEGER m
     *  3. 2D_INTEGER_ARRAY edges
     *  4. INTEGER s
     */

    public static List<Integer> bfs(int n, int m, List<List<Integer>> edges, int s) {
    // Write your code here
        if (n < 1 || edges == null || edges.size() < 1 || s < 1) return null;

        // Step 1
        Set<Integer> [] tree = new Set[n];
        for (List<Integer> edge : edges) {
            int a = edge.get(0);
            int b = edge.get(1);
            if (tree[a-1] == null) {
                tree[a-1] = new HashSet<Integer>();
            }
            tree[a-1].add(b);
            if (tree[b-1] == null) {
                tree[b-1] = new HashSet<Integer>();
            }
            tree[b-1].add(a);
        }

        // Step 2
        List<Integer> res = new ArrayList<Integer>();
        
        // O(n) start from S
        for (int i = 0; i < n - 1; i++) {
            res.add(-1);    
        }
        
        Set<Integer> root = tree[s-1];
        if (root == null) return res;
        
        Deque<Integer> queue = new LinkedList<Integer>();
        for (Integer r : root) {
            queue.add(r);
        }
        int height = 1;
        boolean [] visited = new boolean [n];
        visited[s-1] = true;
        while (!queue.isEmpty()) {
            Deque<Integer> queuen = new LinkedList<Integer>();
            while (!queue.isEmpty()) {
                int v = queue.poll().intValue();
                if (!visited[v-1]) {
                    visited[v-1] = true;
                    // update distances
                    if (v > s)
                        res.set(v-2, height*6);
                    else 
                        res.set(v-1, height*6);
                    if (tree[v-1] != null) {
                        for (Integer r : tree[v-1]) {
                            queuen.add(r);
                        } 
                    }
                } 
            }
            queue = queuen;
            height++;
        }
        
        // return res
        return res;
    }

}

  • dorirgob
     + 0 comments

    Java 15:

    public static List<Integer> bfs(
    int n, int m, List<List<Integer>> edges, int s) {
  List<List<Integer>> graph = new ArrayList<>();
  List<Integer> distances = new ArrayList<>();

  for (int i = 0; i <= n; i++) {
    graph.add(new ArrayList<>());
  }

  for (List<Integer> edge : edges) {
    graph.get(edge.get(0)).add(edge.get(1));
    graph.get(edge.get(1)).add(edge.get(0));
  }

  int[] dist = bfsExplore(n, s, graph);
  System.out.println(Arrays.toString(dist));
  for (int i = 1; i <= n; i++) {
    if (i != s) {
      distances.add(dist[i]);
    }
  }
  return distances;
}

private static int[] bfsExplore(int n, int s, List<List<Integer>> graph) {
  int weight = 6;
  int[] distances = new int[n + 1];
  Arrays.fill(distances, -1);
  boolean[] visited = new boolean[n + 1];
  Queue<int[]> queue = new LinkedList<>();
  queue.offer(new int[] {s, 0});
  visited[s] = true;

  while (!queue.isEmpty()) {
    int[] current = queue.poll();
    distances[current[0]] = weight * current[1];

    for (int neighbor : graph.get(current[0])) {
      if (!visited[neighbor]) {
        queue.offer(new int[] {neighbor, current[1] + 1});
        visited[neighbor] = true;
      }
    }
  }
  return distances;
}

  • zoyashah41306
     + 0 comments

    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.

  • valerius1001
     + 0 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();

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

    }

  • samarthgaba27
     + 0 comments

    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:]