CODEWITHSUNDEEP
javagraphqueueset
nitiger
nitiger

Reputation: 359

How to find the reachability of a graph using set and queue

I'm having some trouble finding all nodes accessible from a given node. Barring the use of DFS or BFS, I'm trying to use a set and a queue to generate all reachable nodes. From what I understand I can initialize the queue to the start node and then add the start node to a set and remove it from the queue. If it is successfully added into the set (not duplicate) then add its reachable nodes back into the queue. Repeat this until the queue is empty and then return the set.

public static Set<String> reachable (Map<String, Set<String>> graph, String startNode) {
         //Set of nodes accessible from the startNode
         Set<String> reachableNodes = new ArraySet<String>();

         //Queue of accessible nodes from a given node to search from.
         Queue<String> searchNodes = new ArrayQueue<String>(graph.get(startNode));

         //Stuck here.

         return reachableNodes;
}

I've become a bit stuck in the implementation. What I've tried is declaring an iterator to iterate through the queue. And while the queue has another element I add that element to the set and remove the element from the queue. But I'm uncertain as to how I can add all the accessible nodes from that element that was just placed into the set back into the queue.

Algorithm (similar to BFS):

  1. Visit node.
  2. Add all nodes accessible from this node to queue.
  3. Add one node from queue to a set of accessible nodes from beginning.
  4. Remove node from queue.
  5. Add all nodes accessible from the node, that was just added from the queue into the set, back into the queue.
  6. Repeat until queue is empty.

Sample:

{ c : [f,e] ,
  f : [g,d] ,
  e : [d]   ,
  d : [g]   }

"Enter startNode: c"
add f,e -> queue
remove f from queue
add f to set
add g d to queue
remove e
add e to set 
add d to queue   
loop until queue is empty.

Upvotes: 0

Views: 1913

Answers (1)

Cory Kendall
Cory Kendall

Reputation: 7314

Generally speaking, the algorithm you're describing is BFS. You can do this using a while loop in your "Stuck" section:

while (searchNodes.peek() != null) {
    String next = searchNodes.remove();
    boolean isNewNode = reachableNodes.add(next);
    if (isNewNode && graph.containsKey(next)) {
        for (String node : graph.get(next)) {
            searchNodes.add(node);
        }
    }
}

Upvotes: 1

Related Questions