BFS: Shortest Reach in a Graph

Sort by

recency

|

312 Discussions

|

  • + 0 comments

    Java Solution using a Graph class:

    public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scanner = new Scanner(System.in);
        int q = scanner.nextInt();
    
        while (q-- > 0){
            int n = scanner.nextInt();
            int m = scanner.nextInt();
    
            Graph graph = new Graph(n);
    
            for (int i = 0; i < m; i++){
                int u = scanner.nextInt();
                int v = scanner.nextInt();
                graph.addEdge(u, v);
            }
    
            int start = scanner.nextInt();
            int[] distances = graph.bfs(start);
    
            for (int i = 1; i <= n; i++){
                if (i != start){
                    System.out.print(distances[i] + " ");
                }
            }
            System.out.println();
        }
        scanner.close();
    }
    

    }

    class Graph { private final Map> adjList = new HashMap<>(); private final int numNodes;

    public Graph(int numNodes){
        this.numNodes = numNodes;
        for (int i = 1; i <= numNodes; i++){
            adjList.put(i, new ArrayList<>());
        }
    }
    
    public void addEdge(int u, int v){
        adjList.get(u).add(v);
        adjList.get(v).add(u);
    }
    
    public int[] bfs(int start){
        int[] distances = new int[numNodes + 1];
        Arrays.fill(distances, -1);
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
    
        queue.add(start);
        visited.add(start);
        distances[start] = 0;
    
        while (!queue.isEmpty()){
            int current = queue.poll();
            for (int neighbor : adjList.get(current)){
                if (!visited.contains(neighbor)){
                    visited.add(neighbor);
                    distances[neighbor] = distances[current] + 6;
                    queue.add(neighbor);
                }
            }
        }
        return distances;
    }
    

    }

  • + 0 comments

    Java Solution using a Graph class:

    class Graph { private final Map> adjList = new HashMap<>(); private final int numNodes;

    public Graph(int numNodes){
        this.numNodes = numNodes;
        for (int i = 1; i <= numNodes; i++){
            adjList.put(i, new ArrayList<>());
        }
    }
    
    public void addEdge(int u, int v){
        adjList.get(u).add(v);
        adjList.get(v).add(u);
    }
    
    public int[] bfs(int start){
        int[] distances = new int[numNodes + 1];
        Arrays.fill(distances, -1);
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
    
        queue.add(start);
        visited.add(start);
        distances[start] = 0;
    
        while (!queue.isEmpty()){
            int current = queue.poll();
            for (int neighbor : adjList.get(current)){
                if (!visited.contains(neighbor)){
                    visited.add(neighbor);
                    distances[neighbor] = distances[current] + 6;
                    queue.add(neighbor);
                }
            }
        }
        return distances;
    }
    

    }

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

    };

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

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