Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 5 M

Year: Dec 2014

Graph is a non-linear data structure which contains a set on vertices and edges that connect them. Traversing a graph means visiting each node individually and processing it. There are two methods of graph traversal i.e. Breadth first search and Depth first search. These algorithms are specified below.

Breadth first search (BFS):

The breadth first search uses a queue data structure for implementation. Here the traversal begins at the root node and explores all neighbouring nodes.

Input: Adjacency matrix

i. Make all nodes in Graph G with state as READY

ii. Initialize queue q

iii. Add the node A (starting node) to the queue.(i.e. Enqueue)

iv. Set node A status as WAITING

v. Repeat vi - ix until queue q is empty.

vi. Remove node N from queue (Dequeue)and process it

vii. Set its status to PROCESSED

viii. Enqueue all the neighbours of N that are in READY state.

ix. Change the state of such neighbours to WAITING.

x. LOOP

xi. END

Depth first search(DFS):

DFS traversal is implemented using stacks. Here we process a node A. Next we process a neighbour of a say A1. Next we process a neighbour of A1 say A2 and so on until we find node which has already been processed or we reach the end. From there we backtrack to the most recent unexplored node.

i. Make all nodes in Graph G with state as READY

ii. Initialize the stack.

iii. Push the starting node A into the stack.

iv. Set its status as WAITING.

v. Repeat vi-x until stack is empty.

vi. Pop a single node N from the top of stack.

vii. Process this node.

viii. Set its status as PROCESSED.

ix. Push all the nodes into the stack that are neighbours of N and are in READY state.

x. Change the state of such nodes as WAITING.

xi. LOOP

xii. END