Your task is to implement Prim\'s algorithm for undirected graphs, using a binom
ID: 3583693 • Letter: Y
Question
Your task is to implement Prim's algorithm for undirected graphs, using a binomial heap as the basis for a priority queue. Input Your program will process a file containing a description of a graph. A graph description contains an arbitrary number of edge descriptions. An edge description consists of two vertices (optionally followed by a weight) followed by a semicolon. A vertex is simply a non-negative integer. If a weight is omitted, a weight of 1 should be assumed. A weight is a positive integer. The file should be free format; whitespace may appear anywhere. Here a sample graph description: 1 5 ; 2 10 23 ; 214 33 1 ; which is equivalent to: 1 5 ; 2 10 23 ; 214 33 1 ; In this example there are six vertices, named 1, 2, 5, 10, 33, and 214, and three edges, 1 to 5, 2 to 10 and 214 to 33, with weights 1, 23, and 1, respectively. The name of your executable must be prim and the name of the file describing the graph will be passed to your program as a command line argument, as in: $ cat g1 1 2 1 ; 2 3 2 ; 3 1 3 ; $ prim g1 [output appears here] Your program should interpret the graph description as an undirected graph and should report a forest of minimum spanning trees that cover all vertices. Read your file twice. The first pass gives you the value of the largest vertex. You can build fixed sized arrays based upon this value. Your arrays may be sparsely populated, but that's OK for this project. Execution If more than one edge is eligible to be added at any given point, chose the edge with the smaller predecessor vertex number, breaking further ties with the smaller successor vertex number . For example, if 13 is the smallest edge weight among the candidate edges and there are these edges with weight 13 available (predecessor listed first): 3 5 13 ; 2 8 13 ; 2 9 13 ; then the 2-8 edge would be added first, followed by the 2-9 edge, followed by the 3-5 edge. Output The output of your program should be a spanning forest, with each tree displayed as a breadth-first traversal along with its weight. Trees are presented in increasing order, based upon the smallest vertex in the tree. Here is an example display: $ cat g2 10 0 9 ; 6 7 11 ; 5 9 1 ; 4 8 7 ; 10 8 6 ; 11 12 2 ; 1 6 5 ; 0 6 10 ; 0 5 3 ; 0 4 8 ; 0 3 2 ; 0 1 4 ; $ prim g2 0 : 0; 1 : 1(0)4, 3(0)2, 4(0)8, 5(0)3; 2 : 6(1)5, 8(4)7, 9(5)1; 3 : 7(6)11, 10(8)6; weight: 47 0 : 11; 1 : 12(11)2; weight: 2 $ For each tree in the forest, you should perform a breadth-first (level-order) traversal, rooted at the smallest vertex. Each level of the traversal starts with the level number (level 0 is the first level) and a colon and is followed by a comma separated list of vertex descriptions. A vertex description is the vertex followed by its breadth-first-search predecessor (in parentheses) followed by the weight of the edge from the predecessor to the vertex in question. The vertex descriptions in a level are to be ordered by increasing vertex number. Each level is terminated by a semicolon. You must follow the format exactly as diff will be used to assess your output. Program organization You must implement the your binomial heap as a separate module named binheap.c and binheap.h. You must define the following methods: binheap *newBinHeap(int (*)(void *,void *)); node *insertBinHeap(binheap *,void *); node *decreaseKeyBinHeap(binheap *,node *,void *); void *extractBinHeap(binheap *); Your binomial heap module is to be generic. That is to say, you can store any kind of (pointer) data in the heap. The constructor newBinHeap takes in a comparison function, which will allow it to work on any kind of data. A comparator for an vertex class might will look something like this: int vertexComparator(void *a,void *b) { //cast from the generic type to the actual type vertex *v = (vertex *) a; vertex *w = (vertex *) b; //return a positive number if v's key > w's //return a zero if they are equal (break ties with vertex numbers) //return a negative number if if v's key < w's ... } The vertex comparator function should, of course, reside in your vertex class, not in your binheap class. A call to the binheap constructor might look like: binheap *h = newBinHeap(vertexComparator); Other details You must implement your program in C. Only the most foolish student would not recompile and thoroughly test the implementation on a Linux system. You must provide a makefile which responds properly to the commands make, make prim, make test, and make clean.
Explanation / Answer
/* SHORTEST PATH */
/* SPATH.C */
# include<stdio.h>
# define size 10
# define infinity 9999
int a[size][size];
int m[size][size];
int i,k,j;
int n;
void Input ();
void Short ();
void Output ();
/* Input function */
void Input()
{
printf(" Input the number of vetices: ");
scanf("%d", &n);
printf(" Input adjacency matrix ");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &a[i][j]);
}
printf(" ");
}
printf(" Adjacency matrix ");
for ( i = 0; i < n; i++)
{
for ( j = 0; j < n; j++)
{
printf(" %i", a[i][j]);
}
printf(" ");
}
}
/* Output function */
void Output()
{
for ( i = 0; i < n; i++)
{
for ( j = 0; j < n; j++)
{
printf(" %d", m[i][j]);
}
printf(" ");
}
}
/* Shortest path function */
void Short ()
{
/* Initialization of matrix m */
for ( i = 0; i < n; i++)
{
for ( j = 0; j < n; j++)
{
if (a[i][j] == 0)
m[i][j] = infinity;
else
m[i][j] = a[i][j];
}
}
printf(" Adjacency matrix after replacing zeros by very large value");
Output();
/* Shortest path evaluation start from here */
for ( k = 0; k < n; k++)
{
for ( i = 0; i < n; i++)
{
for ( j = 0; j < n; j++)
{
if ( m [i][j] <= m [i][k] + m [k][j] )
m [i][j] = m [i][j];
else
m [i][j] = m[i][k] + m [k][j];
}
}
printf(" STEP %d ", k);
Output();
}
}
/* Function main */
void main()
{
Input();
Short();
printf(" Shortest path matrix is as follows ");
Output();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.