BFS: Shortest Reach in a Graph

Sort by

recency

|

310 Discussions

|

  • + 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;
        }
    

    };

  • + 1 comment

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

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