Assignment 11

/* * @author Tenzin Dakpa * @mat no. 5751 * @Assignment 11 * @date 10 may 2009 *------------------------------------------------------------------------* This solution uses Prims MST algorithm with an array based priority queue. * Therefore it is useful only for trivial cases.It further uses a adjacency matrix * to do the graph traversal.However, this solution is simple and easy to impliment. * This priority queue does not require any additional memory as it is performed on * the global array V of pointer to verteces.One can replace this simplistic * priority queue with one base on assignment 4 task 1 or task 2, or maybe even a * soft heap to get a linear time performance. */ #include <stdio.h> #include <malloc.h> #define N 7 #define INFINITY 65000 typedef enum {FALSE, TRUE} bool; typedef struct vertex { char name; struct vertex* pred;// int dist; at infinity bool queued; } Vertex; Vertex* V[N]; /* road length matrix */ int Adj[N][N] = { /*A B C D E F G */ {00,42,20,15,00,00,00}, // {42,00,00,45,17,00,00}, // {20,00,00,00,00,18,00}, // {15,45,00,00,50,05,00}, // {00,17,00,50,00,00,26}, // {00,00,18,05,00,00,12}, // {00,00,00,00,26,12,00}, // };

index of previous vertex in the traversal // the cost of MST branch to this vertex, initially // enables integration of the priority queue // array of all vertexes

A B C D E F G

void init (void); // initialise the Vertex int getMinIndex (void); //the priority queue function. void minspanTree (void);// the MST algorithm as per Prim using a array based prioty queue void printRoad (void); // print the road needed to be covevered with their cost. int main() /*---------------------main----------------------------*/ { init(); minspanTree(); printRoad();

} /*-----------------end-of-main---------------------------*/ /*--------------------------initialise the vertex -----------------------------------------------*/ void init(void) { int i; char names [N+1]="ABCDEFG"; for(i = 0; i < N; i++){ V[i]=(Vertex*)malloc(sizeof(Vertex)); V[i]->pred = NULL; V[i]->dist = INFINITY; V[i]->queued = TRUE; V[i]->name=names[i]; } } /*--------------------prority queue get Minimum function ----------------------------------------*/ int getMinIndex()// a simple array base Priority queue { int i=0; int min=INFINITY;// our infinity distance int index=N+1;// index of the minimum element for(i=0;idist< min&&V[i]->queued==TRUE)//check if the distance is minimum if still in queue { index=i; min=V[i]->dist; } } if(indexqueued=FALSE;// deque this house }else{ index =-1;// report that queue is empty } return index; } /*------------------------------Prims MST Algorithm------------------------------------------*/ void minspanTree() { V[0]->dist=0; int temp; while((temp=getMinIndex())!=-1)//for all element in the queue { int i=0; for(i=0;i0&&V[i]->queued==TRUE) //if the neighboring house is not already connected with a road( that is , has not been taken out of queue) {

house.

if(V[i]->dist>Adj[temp][i]) //check if the current road is the shortest road to that {

V[i]->pred=V[temp];// if yes, we add this shortest path to our MST and set the predecessor V[i]->dist=Adj[temp][i]; } } } } } /*------------------------------Print all the road -------------------------------------------*/ void printRoad() { int i=N-1; int cost=0; while(i>0){ printf("\n connect a road from %c to %c costing %d", V[i]->name,V[i]->pred>name,V[i]->dist); cost =cost+V[i]->dist; i--; } printf("\n total min cost = %d ", cost); }