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
.
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
(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.)
(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.)
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 stack *adj_list; 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++) pv->adj_list=create_stack(); for(pe=e; pe-e<m; pe++) { push_on_stack(v[pe->end1].adj_list, pe); push_on_stack(v[pe->end2].adj_list, 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); while(stack_is_empty(new_vertex->adj_list)==FALSE) { pe=top_of_stack(new_vertex->adj_list); pop_stack(new_vertex->adj_list); 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
(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.)
(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.)