Search

Sunday, February 22, 2015
0 comments

C language: Searching in graph

6:17 AMSunday, February 22, 2015
Similar to traversal of graph two searching techniques of the graph are used which are Breadth First Search and Depth First Search. Both the techniques are same as respective traversal techniques. In case of breadth first search the traversal algorithm for breadth first is used. The algorithm is terminated with a message search successful whenever the deleted item from QUEUE is the node to be searched otherwise the algorithm is terminated with a message search unsuccessful when the QUEUE is empty. The formal algorithm for BFS is:

GRAPHBFS
[goal node is the node to be searched]
Mark the start node and insert it in the QUEUE
If the start node is the goal node Then:
Write: 'Search Successful' ; Exit
[End of If]
Repeat While QUEUE is not empty
Delete QUEUE
If deleted node is the goal node Then:
Write: ' Search successful;; Exit.
Else
Mark the unmarked adjacent nodes of the deleted node.
Insert the marked nodes(if any) of the deleted node in the QUEUE.
[End of If]
[End of While]
Write: 'Search unsuccessful'
Exit.

In case of depth first search the traversal algorithm for depth first is used. The algorithm is terminated with a message search successful whenever the popped item from STACK  is the node to be searched otherwise the algorithm is terminated with a message search unsuccessful when the STACK is empty. The formal algorithm for DFS is:

GRAPHDFT
[goal node is the node to be searched]
Mark the start node and push it on to the STACK
If the start node is the goal node Then:
Write: 'Search Successful'; Exit
[End of If]
Repeat While STACK is not empty
POP STACK.
If popped node is the goal node Then:
Write: ' Search successful'; Exit.
Else
Mark the unmarked adjacent nodes of the popped node. 
Push the marked nodes of the deleted node(if any) on to the STACK.
[End of While]
Write: 'Search unsuccessful'
Exit. 
Protected by Copyscape Online Copyright Protection Software

0 comments :

Post a Comment

 
Toggle Footer
Top