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

Answers

This answer is not selected as best answer. This answer may not be sufficient for exam.

Your limit has been exceed. We have implemented this system because, We got difficulty on managing our servers. Please donate some amount to remove this limit.

Quota: 0 / 30

Donate

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)
{
    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:

User Loaded Image | CSIT Guide

Choose a as initial vertex then we have

User Loaded Image | CSIT Guide

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

User Loaded Image | CSIT Guide

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:

User Loaded Image | CSIT Guide

Choose a as initial vertex then we have

User Loaded Image | CSIT Guide

User Loaded Image | CSIT Guide

User Loaded Image | CSIT Guide

User Loaded Image | CSIT Guide

User Loaded Image | CSIT Guide

If you found any type of error on the answer then please mention on the comment or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .