# 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 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 } -----

Assignment Help Features

- 24 x 7 Availability.
- Plagiarism Free.
- Trained and Certified Experts.
- Deadline Guaranteed.
- Privacy Guaranteed.
- Assignment Help Reward
- Online help for all project.
- Service for everyone
- Online Tutoring
- Free download.
- Whitepaper.

Assignment Help Services

- Assignment Help
- Homework Help
- Writing Help
- Academic Writing Assistance
- Editing Services
- Plagiarism Checker Online
- Proofreading
- Research Writing Help

Calculator