### C language: Searching in graph

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.

## Comments

## Post a Comment