Data Structures and Algorithms - Old Questions

3. Discuss depth first and breadth first traversal of a graph with suitable example.

Traversing a graph means visiting all the vertices in a graph exactly one. In graph all nodes are treated equally. So the starting nodes in graph can be chosen arbitrarily.

A graph traversal finds the edges to be used in the search process without creating loops that means using graph traversal we visit all vertices of graph without getting into looping path.

Breadth First Search Traversal (BFS)

The traversal starts at a node v, after marking the node the traversal visits all incident edges to node v after marking the nodes and then moving to an adjacent node and repeating the process. The traversal continues until all unmarked nodes in the graph has been visited. A queue is maintained in the technique to maintain the list of incident edges and marked nodes.

Algorithm:

BFS(G,s) /* s is start vertex */

{

    T = {s};

    L =Φ; /* an empty queue */

    Enqueue(L,s);

    while (L != Φ )

    {

      v = dequeue(L);

       for each neighbor w to v

            if ( wÏ L and w Ï T )

            {

                enqueue( L,w);

                T = T U {w};     /* put edge {v,w} also */

            }

    }

}

Example:

Choose a as initial vertex then we have

Order the vertices of level 1 i.e. {b, c, g, e, f}. Say order be {e, f, g, b, c}.

Depth First Traversal (DFS)

This technique picks up a node and marks it. An unmarked adjacent node to previous node is then selected and marked, become the new start node, possibly leaving the previous node with unexplored edges for the present. The traversal continued recursively, until all unmarked nodes of the current path are visited. The process is continued for all the paths of the graph. If this cannot be done, move back to another vertex and repeat the process. The whole process is continued until all the vertices are met. This method of search is also called backtracking. A stack data structure is maintained in the technique to maintain the list of incident edges and marked nodes.

Algorithm:

DFS(G,s)

{

    T = {s};

    Traverse(s);

}

Traverse(v)

{

    for each w adjacent to v and not yet in T

    {

        T = T ∪ {w};     //put edge {v, w} also

        Traverse (w);

    }

}

Example:

Choose a as initial vertex then we have