DFS(Depth First Search) & BFS(Breath First Search) in C
DFS v/s BFS
Depth First Search
Depth First Search for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array.
Pseudocode:
Input: A graph G and a vertex v of G
Output: All vertices reachable from v labeled as discovered
1 procedure DFS(G,v):
2 label v as discovered
3 for all edges from v to w in G.adjacentEdges(v) do
4 if vertex w is not labeled as discovered then
5 recursively call DFS(G,w)
The order in which the vertices are discovered by this algorithm is called the lexicographic order.
A non-recursive implementation of DFS with worst-case space complexity O(|E|):
1 procedure DFS-iterative(G,v):
2 let S be a stack
3 S.push(v)
4 while S is not empty
5 v = S.pop()
6 if v is not labeled as discovered:
7 label v as discovered
8 for all edges from v to w in G.adjacentEdges(v) do
9 S.push(w)
Breath First Search
Breath First Search for a graph is similar to Breadth First Traversal of a tree .The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. For simplicity, it is assumed that all vertices are reachable from the starting vertex.
Pseudocode:
Breadth first traversal is accomplished by enqueueing each level of a tree sequentially as the root of any subtree is encountered. There are 2 cases in the iterative algorithm.
- Root case : The traversal queue is initially empty so the root node must be added before the general case.
- General case: Process any items in the queue, while also expanding their children, stop if the queue was empty. The general case will halt after processing the bottom level as leaf nodes have no children.
Input: A search problem. A search-problem abstracts out the problem specific requirements from the actual search algorithm.
Output: An ordered list of actions to be followed to reach from start state to the goal state.
Below is a Python listing for a breadth first problem, where the exact nature of the problem is abstracted in the problem object.
def breadth_first_search(problem):
# a FIFO open_set
open_set = Queue()
# an empty set to maintain visited nodes
closed_set = set()
# a dictionary to maintain meta information (used for path formation)
meta = dict() # key -> (parent state, action to reach child)
# initialize
root = problem.get_root()
meta[root] = (None, None)
open_set.enqueue(root)
#For each node on the current level expand and process, if no children (leaf, then unwind)
while not open_set.is_empty():
subtree_root = open_set.dequeue()
#We found the node we wanted so stop and emit a path.
if problem.is_goal(subtree_root):
return construct_path(subtree_root, meta)
#For each child of the current tree process
for (child, action) in problem.get_successors(subtree_root):
#The node has already been processed, so skip over it
if child in closed_set:
continue
#The child is not enqueued to be processed, so enqueue this level of children to be expanded
if child not in open_set:
#create metadata for these nodes
meta[child] = (subtree_root, action)
#enqueue these nodes
open_set.enqueue(child)
#We finished processing the root of this subtree, so add it to the closed set
closed_set.add(subtree_root)
#Produce a backtrace of the actions taken to find the goal node, using the recorded meta dictionary
def construct_path(state, meta):
action_list = list()
#Continue until you reach root meta data (i.e. (None, None))
while meta[state][0] is not None:
state, action = meta[state]
action_list.append(action)
action_list.reverse()
return action_list
Lets have a look on the actual code :)
Comments
Post a Comment