/* prim.c Compute minimum spanning trees of graphs via Dijkstra/Prim's algorithm. */ /* Copyright 2003-2020 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. These programs appear in my books: "The Algorithm Design Manual" by Steven Skiena, second edition, Springer, London 2008. See out website www.algorist.com for additional information or https://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorith01-20 "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information, or https://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include #include #include #include "bfs-dfs.h" #define MAXINT 1000007 int parent[MAXV+1]; /* discovery relation */ /************************************************************/ /* [[[ prim_cut */ int prim(graph *g, int start) { int i; /* counter */ edgenode *p; /* temporary pointer */ bool intree[MAXV+1]; /* is the vertex in the tree yet? */ int distance[MAXV+1]; /* cost of adding to tree */ int v; /* current vertex to process */ int w; /* candidate next vertex */ int dist; /* cheapest cost to enlarge tree */ int weight = 0; /* tree weight */ for (i = 1; i <= g->nvertices; i++) { intree[i] = false; distance[i] = MAXINT; parent[i] = -1; } distance[start] = 0; v = start; while (!intree[v]) { intree[v] = true; if (v != start) { printf("edge (%d,%d) in tree \n",parent[v],v); weight = weight + dist; } p = g->edges[v]; while (p != NULL) { w = p->y; if ((distance[w] > p->weight) && (!intree[w])) { distance[w] = p->weight; parent[w] = v; } p = p->next; } dist = MAXINT; for (i = 1; i <= g->nvertices; i++) { if ((!intree[i]) && (dist > distance[i])) { dist = distance[i]; v = i; } } } return(weight); } /* ]]] */ int main(void) { graph g; int weight; read_graph(&g, false); weight = prim(&g, 1); printf("Out of Prim: weight = %d \n",weight); return 0; }