Application Development, Product to Market
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use

Algorithm - BFS & DFS

6/12/2014

0 Comments

 
Picture
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 
Picture

complete source in java

references

  • Breadth first search and depth first search
  • Depth First Search Algorithm
  • Breadth First Search Algorithm
0 Comments



Leave a Reply.

    Categories

    All
    Algorithm
    Concurrency
    CQ
    Data Structure
    Design Pattern
    Developer Tool
    Dynamic Programming
    Entrepreneur
    Functional Programming
    IDE
    Java
    JMX
    Marketing
    Marklogic
    Memory
    OSGI
    Performance
    Product
    Product Management
    Security
    Services
    Sling
    Social Media Programming
    Software Development

    Feed Widget

    Archives

    May 2020
    March 2020
    April 2018
    March 2018
    February 2018
    December 2017
    March 2017
    November 2016
    June 2016
    May 2016
    April 2016
    October 2015
    September 2015
    August 2015
    September 2014
    July 2014
    June 2014
    May 2014
    March 2014
    January 2014
    December 2013
    November 2013
    October 2013
    September 2013
    August 2013
    July 2013
    June 2013

    RSS Feed

in loving memory of my mother  and my 4th aunt
Photos used under Creative Commons from net_efekt, schani, visnup, Dan Zen, gadl, bobbigmac, Susana López-Urrutia, jwalsh, Philippe Put, michael pollak, oskay, Creative Tools, Violentz, Kyknoord, mobilyazilar