Algorithm - BFS & DFS - From Passion to Profession

Algorithm - BFS & DFS

6/12/2014

Queue and Stack are basic data structure. This post is about implementing Breadth First Search (BFS) & Depth First Search (DFS) using concept of Queue and Stack.

the approach

Whether BFS or DFS, we need a data structure to track which node to check next for unvisited adjacent nodes to traverse. A very important concept to keep in mind here is that the chosen data structure is a place to keep track of nodes that had just been visited, of which their unvisited adjacent nodes will be traverse next. No node should be put into the data structure more than once since no node should have been visited twice.

Now back to the data structure, for such a data structure, BFS needs use a Queue for tracking visited nodes and what adjacent nodes to check next in a breadth-first way of visiting. The order of the nodes in the queue is the order to check for their unvisited adjacent children. On the other hand, a DFS needs a Stack for tracking just-visited nodes and what adjacent nodes to check next in a depth-first way of traversing.

thought process

Breadth First Search (BFS)

A Queue has FIFO (first-in-first-out) nature. In Java, use LinkedList class for queue.

Start from the root node, enqueue it as the first step. In general, you want to enqueue just-visited children nodes in a breadth first algorithm. For each node in the queue, all the children nodes of a node will be checked for their unvisited adjacent nodes to be enqueued and then mark visited. Only unvisited node should be visited, enqueued, then be marked as visited immediately after being enqueued. En-queuing node is a way to say that the node has just been visited in a BFS approach, the children of each node in the queue will be checked for its children. No node will be enqueued more than once because no node will be visited twice.

To find the next node to traverse, dequeue to get a visited node to search for all its adjacent unvisited candidates. Dequeue a node means none of its child worth being checked for unvisited nodes any more. Once found such unvisited child nodes, enqueue them then and make them visited, so these just visited nodes will be checked for their unvisited adjacent nodes later. The process goes on until nothing left in the queue.

Depth First Search (DFS)

A Stack has FILO (first-in-last-out) nature. In Java, use Stack class for Stack.

Start from the root node, push it into the Stack. For nodes in the Stack, each of node's unvisited children nodes will be traversed eventually. In general, you want to push only 'one' child of a just-visited node so that child node will be checked for its one unvisited adjacent node to go deeper into the tree. Pushing a node means the node has just been visited. When checking for unvisited child nodes, 'peek' the Stack for a just-visited candidate to search for its unvisited child nodes. Only 'pop' when a just-visited node has absolutely no more unvisited child to go deeper into the tree traversal.

code walk-through

Of course we must have a Node class. The node has its value, children, and also a flag to indicate whether itself is marked visited or not, among other member functions.

public static class Node{
private int value;
private ArrayList<Node> child_nodes = new ArrayList<Node>();
public boolean visited = false;

public Node(int value){
this.value = value;
}

public String toString(){
return Integer.toString(value);
}

public ArrayList<Node> getAllChildNodes(){
return child_nodes;
}

public Node getOneUnvisitedChildNode(){
for(Node n: child_nodes){
if (n.visited == false){
return n;
}
}
return null;
}

public ArrayList<Node> getUnvisitedChildNodes(){
ArrayList<Node> unvisited_nodes= new ArrayList<Node>();
for(Node n: child_nodes){
if (n.visited == false){
unvisited_nodes.add(n);
}
}
return unvisited_nodes;
};

public Node addChild(Node n){
child_nodes.add(n);
return Node.this;
}
}

Then I implemented a Strategy base class for BFS and DFS strategy to inherit from. The only member function, markTreeUnvisited(Node n), offers a way to clear flags of the whole tree, assuming there's no loop in the tree :

public static class TraverseStrategy{

public static void markTreeUnvisited(Node n){
n.visited = false;
for(Node c: n.getAllChildNodes()){
markTreeUnvisited(c);
}
}
}

Then the BFS and DFS Strategy:

public static class BFSStrategy extends TraverseStrategy{
public static void search(Node n){
markTreeUnvisited(n); // mark all nodes unvisited

LinkedList queue = new LinkedList<Node>();
queue.add(n);
System.out.println(n);

while(!queue.isEmpty()){
Node node = (Node) queue.remove();
for(Node c:node.getUnvisitedChildNodes()){
queue.add(c); // enqueue
System.out.println(c); // visit the node
c.visited = true; // immediately mark visited
}
}
}
}

public static class DFSStrategy extends TraverseStrategy{
public static void search(Node n){
markTreeUnvisited(n); // mark all nodes unvisited

Stack stack = new Stack<Node>();
stack.push(n);
System.out.println(n);

while(!stack.isEmpty()){
Node node = (Node) stack.peek();
Node unvisited_child_node = node.getOneUnvisitedChildNode();
if (unvisited_child_node != null){
stack.push(unvisited_child_node); // push
System.out.println(unvisited_child_node); // visit the node
unvisited_child_node.visited = true; // immediately mark visited
}
else{
stack.pop();
}
}
}
}

Finally, my main program that set up the tree, then perform BFS and DFS:

public static void main (String[] args) throws java.lang.Exception
{

// initialize the tree
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
Node root_node = n1;
n1.addChild(n2).addChild(n3).addChild(n4);
n2.addChild(n6);
n3.addChild(n5).addChild(n6);
n4.addChild(n6);

System.out.println("BFS:");
BFSStrategy.search(root_node);
System.out.println("DFS:");
DFSStrategy.search(root_node);
}

Output:

BFS: 1 2 3 4 6 5
DFS: 1 2 6 3 5 4

complete source in java

references

0 Comments