The Complete Codes

C Program For Prim's Algorithm To Find Shortest Path #include <stdio.h> #include <stdlib.h> #define infinity 9999 #define MAX 20 int G [ MAX ][ MAX ], spanning [ MAX ][ MAX ], n ; int prims (); int main () {     int i , j , total_cost ;     printf ( "Enter no. of vertices:" );     scanf ( " %d " , & n );     printf ( " \n Enter the adjacency matrix: \n " );     for ( i = 0 ; i < n ; i ++)         for ( j = 0 ; j < n ; j ++)             scanf ( " %d " , & G [ i ][ j ]);     total_cost = prims ();     printf ( " \n spanning tree matrix: \n " );     for ( i = 0 ; i < n ; i ++)     {         printf ( " \n " );         for ( j = 0 ; j < n ; j ++)             printf ( " %d \t " , spanning [ i ][ j ]);     }     printf ( " \n\n Total cost of spanning tree= %d " , total_cost );     return 0 ; } int prims () {     int cost [ MAX ][ MAX ];     int u ,

Directed Acyclic Graph (DAG) DAG, here directed means that each edge has an arrow denoting that the edge can be traversed in only that particular direction. Acyclic means that the graph has no cycles, i.e., starting at one node, you can never end up at the same node. DAG can be used to find the shortest path from a given source node to all other nodes. To find the shortest path by using DAG, first of all sort the vertices of the graph topologically and then relax the vertices in topological order.

Prim’s Algorithm This is another algorithm for finding MST. The idea behind this algorithm is just take any arbitrary vertex and choose the edge with minimum weight incident on the chosen vertex. Add the vertex and continue the above process taking all the vertices added. Remember the cycle must be avoided. Algorithm: PrimMST(G) { T = ?; // T is a set of edges of MST S = {s} ; //s is randomly chosen vertex and S is set of vertices while(S != V) { e = (u,v) an edge of minimum weight incident to vertices in T and not forming a simple circuit in T if added to T i.e. u ??S and v??V-S T = T ??{(u,v)}; S = S ??{v}; } } Analysis: In the above algorithm while loop execute O(V). The edge of minimum weight incident on a vertex can be found in O(E), so the total time is O(EV). We can improve the performance of the above algorithm by choosing better data structures as priority queue and normally it will be seen that the running time of prim’s algorithm is O(ElogV)!.

Minimum Spanning Tree Given an undirected graph G = (V,E), a subgraph T =(V,E’) of G is a spanning tree if and only if T is a tree. The MST is a spanning tree of a connected weighted graph such that the total sum of the weights of all edges eÎE’ is minimum amongst all the sum of edges that would give a spanning tree.