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

|

697 Discussions

|

  • bensa7044
     + 0 comments

    At Utah Processing Experts, we know that every dollar counts when you’re running a business. That’s why we’re dedicated to providing honest, affordable, and reliable Payment Processing Utah payment processing tailored to Utah business owners.

    Our approach is simple no hidden fees, no long-term contracts, and no surprises. We believe in transparent pricing and next-day funding, so you can access your hard-earned money quickly and confidently. With our Utah-based support team, you’ll always get real help from real people who understand your business and community.

    Whether you operate a retail store, restaurant, or service company, our team will design a payment solution that saves you money and simplifies your operations. We partner with businesses of all sizes to help them grow through smarter, faster, and more transparent payment systems.

  • chroniclestorie1
     + 0 comments

    import java.util.*;

    class ResultAlt {

    /*
 * 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) {
    // Build adjacency list
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
    }
    for (List<Integer> edge : edges) {
        int u = edge.get(0) - 1; // 0-based indexing
        int v = edge.get(1) - 1;
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    // Distance array initialized to -1
    int[] dist = new int[n];
    Arrays.fill(dist, -1);

    // BFS
    Queue<Integer> q = new LinkedList<>();
    q.add(s - 1);
    dist[s - 1] = 0;

    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 6; // edge weight = 6
                q.add(v);
            }
        }
    }

    // Prepare result (excluding source node)
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (i != (s - 1)) {
            result.add(dist[i]);
        }
    }

    return result;
}

    }

  • 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.