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

  • jorgekasa
     + 0 comments

    This is my Java 7 Solution.

    I was in this problem a lot of hours until I began to read again the problem and there I found my error:

    "Consider an undirected graph"

    This was really important because in my case I was just connecting node "source" with "destination" but I didn't connect at the inverse.

    So, this is the code

    public static class Graph {
    HashMap<Integer, Node> nodeLookup = new HashMap<Integer, Node>();
    int size;

    public static class Node {
        int id;
        LinkedList<Node> adjacent = new LinkedList<Node>();

        private Node(int id) {
            this.id = id;
        }
    }

    public Graph(int s) {
        this.size = s;
        for(int i = 0; i < size; i++) {
            Node node = new Node(i);
            nodeLookup.put(i, node);
        }
    }

    public Node getNode(int index) {
        return nodeLookup.get(index);
    }

    public void addEdge(int first, int second) {
        Node s = getNode(first);
        Node d = getNode(second);

        s.adjacent.add(d);
        d.adjacent.add(s);  //THIS IS KEY!!! This is an Unidirectional Graph
    }

    public int[] shortestReach(int startId) { // 0 indexed
        int[] distance = new int[size];
        Arrays.fill(distance, -1);

        LinkedList<Node> toVisit = new LinkedList<Node>();
        HashSet<Integer> visited = new HashSet<Integer>();

        toVisit.add(getNode(startId));
        distance[startId] = 0;

        while(!toVisit.isEmpty()) {
            Node current = toVisit.remove();

            for(Node n: current.adjacent) {
                if(!visited.contains(n.id)){
                    visited.add(n.id);
                    toVisit.add(n);
                    distance[n.id] = distance[current.id] + 6;
                }

            }
        }

        return distance;
    }

}