Data Structures and Algorithms - Old Questions

10. What do you mean by graph traversal? Explain prim's algorithm with 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.

Prim’s Algorithm

Prim's Algorithm is used to find the minimum spanning tree from a graph. Prim's algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized.

This algorithm involves the following steps:

1. Select any vertex in G. Among all the edges which are incident to it, choose an edge of minimum weight. Include it in T.

2. At each stage, choose an edge of smallest weight joining a vertex which is already included in T and a vertex which is not included yet so that it does not form a cycle. Then included it in T.

3. Repeat until all the vertices of G are included with n-1 edges. 

Pseudocode:

T = ∅;
U = { 1 };
while (U ≠ V)
    let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V - U;
    T = T ∪ {(u, v)}
    U = U ∪ {v}