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 < limits.h >    /* 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 course!
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 }
-----
</limits.h>