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 breadthfirst 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 justvisited nodes and what adjacent nodes to check next in a depthfirst way of traversing. thought process
Breadth First Search (BFS)
A Queue has FIFO (firstinfirstout) 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 justvisited 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. Enqueuing 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 (firstinlastout) 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 justvisited 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 justvisited candidate to search for its unvisited child nodes. Only 'pop' when a justvisited node has absolutely no more unvisited child to go deeper into the tree traversal. code walkthrough
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{
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{
Then the BFS and DFS Strategy:
public static class BFSStrategy extends TraverseStrategy{
Finally, my main program that set up the tree, then perform BFS and DFS:
public static void main (String[] args) throws java.lang.Exception
complete source in javareferences
0 Comments
Leave a Reply. 
Categories
All
Archives
December 2017
