BFS: Shortest Reach in a Graph

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

    }