Data Structures and Algorithms - Old Questions

9. What is weighted graph? Explain Depth-first traversal of a graph.

Weighted Graph

A weighted graph is a graph G, in which each edge, e, is assigned a non-negative real number, w(e), called the weight of e. For e.g.

Depth First Traversal (DFS)

Depth-first traversal (DFS) is an algorithm for traversing graph data structures. 

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