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>
Calculator
Simple Calculator
Scientific Calculator
EMI Calculator
Mortgage Calculator
Love Calculator
Percentage Calculator
Currency Calculator
Units Converter
Graph Calculator
Financial Lease Calculator
Temperature Converter
Resources
24 x 7 Availability.
Trained and Certified Experts.
Deadline Guaranteed.
Plagiarism Free.
Privacy Guaranteed.
Free download.
Online help for all project.
Testimonial
Urgenthomework helped me with finance homework problems and taught math portion of my course as well. Initially, I used a tutor that taught me math course I felt that as if I was not getting the help I needed. With the help of Urgenthomework, I got precisely where I was weak: