BFS and DFS
Searching algorithms are extremely important in daily applications. Many searching algorithms have been developed for different types of data structures. Among them, searching on graphs and trees are of particular interests due to their wide application. For instance, the Internet is in the form of graphs. Many data are stored in the form of tree for rapid reference. Two of the most fundamental searching algorithms recommended for beginners are BFS and DFS.
BFS (Breadth First Search) focuses on traversing the tree layer by layer. If we denote N{1} be the set of nodes that can be reached from the root node by 1 taking one step, and we denote N{k} be the set of nodes that are not in N{1}…N{k-1} but can be reached from the nodes in N{k-1} by one step, then BFS basically traverses all nodes in N{i} for i = 1,2,... accordingly.
To implement BFS, we use a queue data structure to store the intermediate nodes. According the FIFO (First-in-First-out) property, every time we dequeue from the queue, we always get the oldest intermediate node. Then we expand it. And when we visited a node, we always indicate it as visited, and enqueue all its neighbor uninvited node to the queue. This way we can always end up traversing the tree layer by layer. If we visit a node that is what we want, we just stop the searching.
Time complexity = O(|V|+|E|) as every vertex and every edge will be visited in the worst case.
Space complexity = O(|V|+|E|) for Adjacency List representation. And O(|V|^2) for Adjacency Matrix representation.
For DFS, we simply explore the path to the end before we return upward to explore another path. When we track back to the parent node and there is another path led from this node, we simply go to that path. And when we reaches the leaf node, we simply turn back again.
DFS can be implemented in two approaches, (i) recursion or (ii) while loop. The ideas are the same: instead of storing intermediate nodes in queue, we push them into a stack. When we pop a stack, we always get the node that arrived the latest.
Denote b = average branching factor, m = max depth of search tree.
Time complexity = O(b^m).
Space complexity = O(mb) if when we visit a node, we push.stack all its neighbours. O(m) if we only push.stack one of the child when we expand the frontier.
For BFS, the space is a big problem. The memory needed will be so large if there are so many nodes in the tree. For DFS, the time becomes the problem. From the point of view of AI, they both cannot search for optimal solution. The two approaches are usually used in competitions like ACM-ICPC due to easy implementation and optimal solutions are not required.
