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.

Graph Traversals There are a number of approaches used for solving problems on graphs. One of the most important approaches is based on the notion of systematically visiting all the vertices and edges of a graph. The reason for this is that these traversals impose a type of tree structure (or generally a forest) on the graph, and trees are usually much easier to reason about than general graphs. Depth First Search This is another technique that can be used to search the graph. Choose a vertex as a root and form a path by starting at a root vertex by successively adding vertices and edges. This process is continued until no possible path can be formed. If the path contains all the vertices then the tree consisting of this path is the DFS tree. Otherwise, we must add other edges and vertices. For this move back from the last vertex that is met in the previous path and find whether it is possible to find a new path starting from the vertex just met. If there is such a path

Graph Traversals There are a number of approaches used for solving problems on graphs. One of the most important approaches is based on the notion of systematically visiting all the vertices and edges of a graph. The reason for this is that these traversals impose a type of tree structure (or generally a forest) on the graph, and trees are usually much easier to reason about than general graphs. Breadth-first search This is one of the simplest methods of graph searching. Choose some vertex arbitrarily as a root. Add all the vertices and edges that are incident in the root. The new vertices added will become the vertices at level 1 of the BFS tree. Form the set of the added vertices of level 1, and find other vertices, such that they are connected by edges at level 1 vertices. Follow the above step until all the vertices are added. Algorithm: BFS ( G , s ) // s is start vertex {     T = {s};     L = Φ; // an empty queue     Enqueue (L, s );     while (L != Φ)     {  

Job Sequencing with Deadline We are given a set of n jobs. Associated with each job I, di>=0 is an integer deadline and pi>=O is profit. For any job i profit is earned if the job is completed by the deadline. To complete a job one has to process a job for one unit of time. Our aim is to find a feasible subset of jobs such that profit is maximum. Example n=4, (p1,p2,p3,p4)=(100,10,15,27),(d1,d2,d3,d4)=(2,1,2,1) n=4, (p1,p4,p3,p2)=(100,27,15,10),(d1,d4,d3,d2)=(2,1,2,1) We have to try all the possibilities, complexity is O(n!). Greedy strategy using total profit as optimization function to above example. Begin with J= Job 1 considered, and added to J ->J={1} Job 4 considered, and added to J -> J={1,4} Job 3 considered, but discarded because not feasible   ->J={1,4} Job 2 considered, but discarded because not feasible   -> J={1,4} The final solution is J={1,4} with a total profit of 127 and it is optimal Algorithm: Assume