CPS 542 Prim’s algorithm Assignment 5

Goal: To implement Prim’s algorithm for finding the minimum cost spanning tree for a given undirected graph using an adjacency matrix representation of the graph. Due:

Constraints:

• use the given define and typedefs
• read graph data from stdin using input redirection
• keep the selected paths in an array of edges
• no file manipulation in any form
• compiles using make/Makefile

Statement:

Write a modular, properly documented C-program to study the above mentioned (in goal). The program should use the specified modules (given below). The input data format is:

{`
size-of-matrix  number of edges start-vertex 
from-vertex  to-vertex  weight ... example:
6  10  0  <<--(size, edges, start)
0  1  16  <<--(from, to,  weight)
0  5  21
0	4  19
1	2  5
1  3  6
1	5  11
2	3  10
3	4  18
3  5  14 4  5  33`}

output:

{`
0	1  16  <<--(first edge)
1	2  5
1  3  6
1  5  11 3  4  18 total cost: 56`}

Globals:

{`
#include      /* for INT_MAX */
#define N 10            /* max matrix size is 10 x 10 */
#define INF INT_MAX     /* infinity?  */ typedef struct edge {
int fromv; int tov; int weight; } edge; Modules needed:
1.	void getdata(int amtrx[][N], int *n; int *stv);   
{ fills amtrx[][] with data edge by edge, all other entries are INF,
returns actual size in n and start vertex in stv }
2.	void prims(int amtrx[][N], int n, edge edgs[]);   
{ finds the MCST and inserts the paths in tree in array edgs, using Prim’s algorithm }
3.	void printpaths(edge edgs[], int n);   
{ prints the paths to stderr, using fprintf()... } 4. int main(void); of Assignment!
The program will be invoked as:
./a5 < graphdatafile ++++>>> Create an inputfile to test your program. 
Code for getdata() module:
void getdata(int amtrx[][N], int *sz, int *stv)
{
int i, j, nsz, nedg, fr, to, vtx, wt;
scanf("%d %d %d", &nsz, &nedg, &vtx);    
for(i = 0; i < nsz; i++)       
for(j = 0; j < nsz; j++)         
am[i][j] = INF;
for(i = 0; i < nedg; i++) {       
scanf("%d %d %d", &fr, &to, &wt);       
amtrx[fr][to] = wt;      
amtrx[to][fr] = wt;    
}
  *sz = nsz;
  *stv = vtx;
}
Turn-in: submit via BB a tar archive  file globalid-a5.tar containing files 
a5/Makefile and a5/a5.c. ---- algorithm--Assumptions:
adjacency matrix  N X N selected[N] initialized to 0’s edges 
seen so far start vertex define INF to large number Cii = INF, 
Cij = INF (if no path to) list of edges (from -> to)
select[start] = 1 edges seen s = 0 while s < N-1 {   
for i = 1 to N{      min = INF      
if select[i] then         for j = 1 to N{
if not select[j] and min > Cij {                 
min = Cij, row = i, col = j            }
        }
     }
   }    sel[col] = 1    add edge 
< row,col,min> to array edgs    increment s } 
-----`}