Graph/MinimumSpanningTree/mst.cxx File Reference

Prim's Algorithm for Minimum Spanning Tree problem. More...

#include <iostream>
#include "BinaryHeap.h"
#include "Graph.h"

Functions

void debug (int n, vector< int > key, vector< int > pred)
 Useful method for Debugging.
void mst_prim (Graph const &graph, vector< int > &pred)
 Compute the Minimum Spanning Tree for the graph and leave results of computation within the computed pred[] array for each vertex.


Detailed Description

Prim's Algorithm for Minimum Spanning Tree problem.

Defines the implementation using Prim's Algorithm to minimum spanning tree problem

Author:
George Heineman
Date:
6/15/08

Function Documentation

void debug ( int  n,
vector< int >  key,
vector< int >  pred 
)

Useful method for Debugging.

void mst_prim ( Graph const &  graph,
vector< int > &  pred 
)

Compute the Minimum Spanning Tree for the graph and leave results of computation within the computed pred[] array for each vertex.

Encoding of MST is done using 'pred' entries.

Parameters:
graph the undirected graph
pred pred[] array to contain previous information for MST.

Algorithm Development Kit 1.0