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. BFS: Shortest Reach in a Graph
  2. Discussions

BFS: Shortest Reach in a Graph

Sort by

recency

|

310 Discussions

|

  • morgehowie
     + 0 comments

    include

    include

    include

    include

    include

    include

    using namespace std;

    class Graph { vector> adjList; int n;

    public:
    Graph(int n) {
        adjList = vector<vector<int>> (n);
        this->n = n;
    }

    void add_edge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    vector<int> shortest_reach(int start) {
        vector<int> shortest_paths = vector<int>(n, -1);

        queue<int> q;
        q.push(start);
        vector<bool> visited(n);
        visited[start] = true;
        int curr_level = 1;
        while(q.size()){
            int level_size = q.size();
            while(level_size--){
                int curr_node = q.front();
                q.pop();
                for(int adj_val: adjList[curr_node]){
                    if(!visited[adj_val]){
                        shortest_paths[adj_val] = curr_level * 6;
                        visited[adj_val] = true;
                        q.push(adj_val);
                    }
                }
            }
            curr_level++;
        }
    return shortest_paths;
}

        return shortest_paths;
    }

    };

  • sqzhng8
     + 2 comments

    "each node is labeled from 1 to n", this is in the first sentence of the description and also shown in the examples, however after spending hours to debug, I found out that in the main() function, it is decrementing the node's label so that it is actually labeled from 0 to n-1.

    I just want to point this out, hopefully it will be helpful. This is for C++.

    int main() { ...... // read and set edges for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--, v--; // add each edge to the graph graph.add_edge(u, v); } int startId; cin >> startId; startId--; // Find shortest reach from node s vector distances = graph.shortest_reach(startId);

  • bordax
     + 0 comments

    Python

    from collections import deque, defaultdict
class Graph:
    def __init__(self, n):
        self.n = n
        self.neighbors = defaultdict(set)
    
    def connect(self, a, b):
        self.neighbors[a].add(b)
        self.neighbors[b].add(a)

    
    def find_all_distances(self, start):
        distances = {}
        queue = deque((n, 1) for n in self.neighbors[start])
        visited = set([start])
        while queue:
            curr_node, dist_from_start = queue.popleft()
            if curr_node in visited:
                continue
            visited.add(curr_node)
            distances[curr_node] = dist_from_start * 6
            queue.extend((n, dist_from_start+1) for n in self.neighbors[curr_node])
        
        for i in range(0, self.n):
            if i == start:
                continue
            print(distances.get(i, -1), end=" ")
        print()

  • oscarvictory30
     + 0 comments

    Kotlin code

    import java.io.*
import java.util.*
import java.util.Scanner.*

fun main(args: Array<String>) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT.
         */
    val query = readln().toInt()
    
    for(i in 0 until query){
        val c = HashMap<Int, HashSet<Int>>()    
        val q: Queue<Int> = LinkedList()
        val nm = readln().split(" ")
        val n = nm[0].toInt()
        val m = nm[1].toInt()
        
        for(i in 0 until m){
            val uv =  readln().split(" ")
            val u = uv[0].toInt()
            val v = uv[1].toInt()
            if(c[u] == null){
                c[u] = HashSet()
            }  
            if(c[v] == null){
                c[v] = HashSet()
            }
            c[u]!!.add(v) 
            c[v]!!.add(u) 
        }
        
        val s = readln().trim().toInt()
        
        val visited = Array(n){0}
        
        q.offer(s)
        
        while(q.isNotEmpty()){
            val node = q.peek()
            c[node]?.forEach{
                if (visited[it - 1] == 0) {
                    visited[it - 1] = visited[node - 1] + 6
                    q.offer(it) 
                } 
            }
            q.poll()  
        }
        
        val sb = StringBuilder()
        for (i in visited.indices){
            val v = visited[i]
            if(i +1 != s ) {
                if (v > 0){
                    sb.append(v)
                } else {
                    sb.append("-1")
                }
                if(i != visited.lastIndex) {
                    sb.append(" ") 
                } 
            } 
        } 
        
        println(sb.toString())
    }
}

  • ketan_patel25
     + 0 comments

    JAva code

    import java.io.*;
import java.util.*;

public class Solution {

    static void BFS(ArrayList<Integer>[] adj, int[] visited, int s) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = 0;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int i = 0; i < adj[node].size(); ++i) {
                int neighbor = adj[node].get(i);

                if (visited[neighbor] == -1) {
                    visited[neighbor] = visited[node] + 6;
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int q = Integer.parseInt(br.readLine());

        for (int i = 0; i < q; ++i) {
            String[] nm = br.readLine().split(" ");
            int n = Integer.parseInt(nm[0]);
            int m = Integer.parseInt(nm[1]);

            ArrayList<Integer>[] adj = new ArrayList[n + 1];
            for (int j = 1; j <= n; ++j) {
                adj[j] = new ArrayList<>();
            }

            for (int j = 1; j <= m; ++j) {
                String[] uv = br.readLine().split(" ");
                int u = Integer.parseInt(uv[0]);
                int v = Integer.parseInt(uv[1]);
                adj[u].add(v);
                adj[v].add(u);
            }

            int s = Integer.parseInt(br.readLine());

            int[] visited = new int[n + 1];
            Arrays.fill(visited, -1);

            BFS(adj, visited, s);

            for (int j = 1; j <= n; ++j) {
                if (visited[j] != 0) {
                    System.out.print(visited[j] + " ");
                }
            }

            System.out.println();
        }
    }
}