Minimum spanning tree algorithms

#### Our input/output conventions

We let `n` denote the number of vertices and we let `m` denote the number of edges. Each vertex is one of the integers `0,1,...,n-1`; each edge is a structure that includes elements
```  int end1;
int end2;
float weight;
```
We represent the output by an array `tree` of pointers to the `n-1` edges of the minimum spanning tree; if the input graph is disconnected, then we set `tree=NULL`.

#### Kruskal's algorithm

This algorithm uses
the ADT Priority Queue and the ADT Union-Find. Each `pq_object` is an edge and its `pq_cost` is its `weight`. Each `uf_object` is a structure `vertex` with elements chosen by the designer of the ADT Union-Find; the `n` structures `vertex` are held in an array , and so they are indexed by `0,1,...,n-1`.
```edge **kruskal(int n, int m, edge e[])
{
vertex *v, *pv, *px, *py;
edge *pe, **tree;
pq *priority_queue;
int edge_count;

v = (vertex *) malloc( n*sizeof(vertex) );
if(v==NULL)
{
printf("OUT OF MEMORY!\n");
exit(1);
}

tree = (edge **) malloc( (n-1)*sizeof(edge *) );
if(tree==NULL)
{
printf("OUT OF MEMORY!\n");
exit(1);
}

for(pv=v; pv-v<n; pv++)
uf_make_set(pv);

priority_queue=create_pq();
for(pe=e; pe-e<m; pe++)
pq_insert(priority_queue, pe, pe->weight);

edge_count=0;
while(edge_count<n-1 && pq_is_empty(priority_queue)==FALSE)
{
pe=find_min(priority_queue);
delete_min(priority_queue);

px=uf_find(v+(pe->end1));
py=uf_find(v+(pe->end2));

if(px!=py)
{
tree[edge_count]=pe;
edge_count++;
uf_union(px,py);
}
}

if(edge_count<n-1)
tree=NULL;
return tree;
}
```
Nice animations of Kruskal's algorithm have been provided by
• Kenji Ikeda
(Scroll down the page and you will find a choice of five different inputs. Repeated clicking on an applet will take you through the algorithm step by step.)
• and by Collette R. Coullard, David S. Dilworth, and Jonathan H. Owen.
(When the applet gets loaded, click on File, the first Open in the menu, and Spanning Tree 1 for a connected input or Spanning Tree 2 for a disconnected input. Then click on Solvers, Spanning Tree in the menu, and Kruskal. Now repeated clicking on Step will take you through the algorithm step by step.)

#### The Prim-Dijkstra algorithm

This algorithm uses
the ADT Priority Queue; we implement each of the `n` adjacency lists as the ADT Stack. The data type `pq_cost` used in the priority queue is `float`. Each `pq_object` is a structure `vertex` that includes elements
```  cost         pq_cost;
struct edge  *best_edge;
char         status;
```
Each `stack_object` is an edge. The values of `status` come from the set of three distinct symbolic constants,
```TREE
FRINGE
UNSEEN
```
```edge **prim_dijkstra(int n, int m, edge e[])
{

vertex *v, *pv, *new_vertex, *other_end;
edge *pe, **tree;
int vertex_count;
pq *priority_queue;

v = (vertex *) malloc( n*sizeof(vertex) );
if(v==NULL)
{
printf("OUT OF MEMORY!\n");
exit(1);
}

tree = (edge **) malloc( (n-1)*sizeof(edge *) );
if(tree==NULL)
{
printf("OUT OF MEMORY!\n");
exit(1);
}

for(pv=v; pv-v<n; pv++)
for(pe=e; pe-e<m; pe++)
{
}

for(pv=v; pv-v<n; pv++)
pv->status=UNSEEN;
priority_queue=create_pq();
vertex_count=0;

pq_insert(priority_queue, v, 0.0);
while(pq_is_empty(priority_queue)==FALSE)
{
new_vertex=find_min(priority_queue);
new_vertex->status=TREE;
vertex_count++;
if(vertex_count>1)
tree[vertex_count-2]=new_vertex->best_edge;

delete_min(priority_queue);
{

other_end=(&v[pe->end1]==new_vertex ?
&v[pe->end2] : &v[pe->end1]);

if(other_end->status==UNSEEN)
{
other_end->status=FRINGE, other_end->best_edge=pe;
pq_insert(priority_queue, other_end, pe->weight);
}
else if(other_end->status==FRINGE &&
pe->weight < other_end->pq_cost)
{
other_end->best_edge=pe;
reduce_cost(priority_queue, other_end, pe->weight);
}
}
}

if(vertex_count<n)
tree=NULL;
return tree;
}
```
Nice animations of the Prim-Dijkstra algorithm have been provided by
• Collette R. Coullard, David S. Dilworth, and Jonathan H. Owen
(When the applet gets loaded, click on File, the first Open in the menu, and Spanning Tree 1 for a connected input or Spanning Tree 2 for a disconnected input. Then click on Solvers, Spanning Tree in the menu, and Prim. Now repeated clicking on Step will take you through the algorithm (with the choice of the starting vertex up to you) step by step; the tree vertices and their best edges are blue; fringe vertices and their best edges are red.)
• and by Kenji Ikeda.
(Scroll down the page and you will find a choice of six different inputs. Repeated clicking on an applet will take you through the algorithm step by step; the tree vertices and their best edges are red; fringe vertices and their best edges are blue.)