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

|

694 Discussions

|

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

  • gbednik
     + 0 comments
    vector<int> bfs(int n, int m, vector<vector<int>> edges, int s) 
{
    // Rearranging edges. my_edges[i] - a list of nodes connected with i-th node
    vector<vector<int>> my_edges(n);
     
    for (auto edge : edges)
    {
        my_edges[edge[0]-1].push_back(edge[1]);
        my_edges[edge[1]-1].push_back(edge[0]);
    }
 
    // Traversing through the graph
    queue<int> my_queue;
    my_queue.push(s);
    
    vector <int> distances(n, -1);
    distances[s-1] = 0;
    int current_dist = 0;
 
    
    while(!my_queue.empty())
    {
        int current_node = my_queue.front();
        
        for(int new_node : my_edges[current_node-1])
        {
            if ( distances[new_node-1] == -1 )
            {
                my_queue.push(new_node);
                distances[new_node-1] = distances[current_node-1] + 6;
            }
        }
        
        my_queue.pop();
    }

    // Removing the start node
    vector<int> ans;
    ans.reserve(n-1);
    
    for(int i = 0 ; i < n ; i++)
    {
        if (i != s-1)
            ans.push_back(distances[i]);
    }

    return ans;
}