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. 



 
Jump to:



 


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




 
Jump to:



 


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 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



 
Jump to:





 
Back to the table of contents of Vašek Chvátal's 
course notes