Let e be the number of edges in the graph.
We may assume that e >= n - 1; otherwise,
the graph is not connected and so has no spanning tree.
It is possible to implement Prim's method so as to have complexity
O(e + n log n).
Such an implementation
requires the use of the adjacency list representation of a graph
as well as the data structure Fibonacci Heap which we
have not studied in this book. An O(e log n)
implementation is possible when the graph is represented
using adjacency lists and we employ a min heap
to assist in the selection of edges.
When an adjacency matrix is used in
conjunction with a min heap, the resulting implementation has
complexity O(n2 + e log n).
Replacing the use
of the modified min heap with a Fibonacci heap will result in an
O(n2) complexity when adjacency
matrices are used and an O(e + n log n) complexity
when adjacency lists are used.
By using the strategy employed in the single-source all-destinations shortest
paths solution of Program 18.3 (i.e., maintain a list of vertices not yet included in
the spanning tree, on each round select the vertex that is closest to
a selected vertex), we obtain an O(n2)
implementation.
This
O(n2) implementation is the
best implementation
to use when the graph has O(n2) edges.
When the number of edges is O(n), for example, it
is advantageous to use adjacency lists together with a
min heap.
When the number of edges is O(n1.5), for example, it
is advantageous to use adjacency lists together with a
Fibonacci heap.
Regardless of whether we use a Fibonacci heap, a min heap, or a
chain of unselected vertices, the basic implementation strategy
is the same.
We begin by adding vertex 1
to the set of selected vertices, that is
the vertices in TV. We go through
n-1 stages. In each of these, a new vertex
is selected. This vertex is the one that is nearest to an already
selected vertex (i.e., it is a vertex that is not in TV
and is connected to a vertex in TV with the
least cost edge). To make this selection, we define, for every
vertex v not in TV,
a distance which equals the cost of the least cost edge
that joins this vertex to any vertex in TV.
At each stage, the vertex with least distance is selected.
Suppose that vertex v is selected, its inclusion
into TV may reduce the distance values of its
adjacent vertices that are currently not in TV.
So we need to perform the operations: select the minimum distance
vertex and decrease some distance values. Alhough these operations
are done best using a Fibonacci heap, they are done fairly efficiently
using either (1) a min heap which is augmented by an array
location to keep track of the
location in heap[] of the distance
value of a vertex or (2) a chain and a distance array as used
in the shortest paths solution of Program 18.3.
First, we develop the implementation
that uses a min heap. We begin by
defining the class ModifiedMinHeap
as below.
The invocation decreaseWeight(x) replaces the
old distance (weight) of vertex x.vertex
by the smaller value x.weight.
The method initialize has not been implemented.
Although the code given below stores weighted edge nodes in the min heap,
it is sufficient to store only the weights.
public class ModifiedMinHeap
{
// data members
WeightedEdgeNode [] heap; // array for complete binary tree
int [] location; // current location of an element
int size; // number of elements in heap
// constructors
/** create a heap with the given initial capacity */
public ModifiedMinHeap(int initialCapacity)
{
if (initialCapacity < 1)
throw new IllegalArgumentException
("initialCapacity must be >= 1");
heap = new WeightedEdgeNode [initialCapacity + 1];
location = new int [initialCapacity + 1];
size = 0;
}
/** create a heap with initial capacity 10 */
public ModifiedMinHeap()
{this(10);}
// methods
/** @return true iff the heap is empty */
public boolean isEmpty()
{return size == 0;}
/** @return number of elements in the heap */
public int size()
{return size;}
/** @return minimum element
* @return null if the heap is empty */
public WeightedEdgeNode getMin()
{
if (size == 0)
return null;
else
return heap[1];
}
/** put theElement into the heap */
public void put(WeightedEdgeNode theElement)
{
// increase array size if necessary
if (size == heap.length - 1)
heap = (WeightedEdgeNode []) ChangeArrayLength.changeLength1D
(heap, 2 * heap.length);
// find place for theElement
// i starts at new leaf and moves up tree
int i = ++size;
while (i != 1 && ((Comparable) heap[i/2].weight)
.compareTo(theElement.weight) > 0)
{
// cannot put theElement in heap[i]
heap[i] = heap[i/2]; // move element down
location[heap[i].vertex] = i;
i /= 2; // move to parent
}
heap[i] = theElement;
location[theElement.vertex] = i;
}
/** remove min element and return it */
public WeightedEdgeNode removeMin()
{
// if heap is empty return null
if (size == 0) return null; // heap empty
WeightedEdgeNode x = heap[1]; // min element
location[x.vertex] = 0;
// restucture heap
WeightedEdgeNode y = heap[size--]; // last element
// find place for y starting at root
int i = 1, // current node of heap
ci = 2; // child of i
while (ci <= size)
{
// heap[ci] should be smaller child of i
if (ci < size && ((Comparable) heap[ci].weight)
.compareTo(heap[ci+1].weight) > 0)
ci++;
// can we put y in heap[i]?
if (((Comparable) y.weight).compareTo(heap[ci].weight) <= 0)
break; // yes
// no
heap[i] = heap[ci]; // move child up
location[heap[i].vertex] = i;
i = ci; // move down a level
ci *= 2;
}
heap[i] = y;
location[y.vertex] = i;
return x;
}
/** decrease weight of x.vertex to x.weight */
public void decreaseWeight(WeightedEdgeNode x)
{
// check if x.vertex in heap
if (location[x.vertex] == 0)
// not in heap
throw new IllegalArgumentException
("illegal id value");
// make sure new distance is smaller
if (((Comparable) x.weight)
.compareTo(heap[location[x.vertex]].weight) >= 0)
throw new IllegalArgumentException
("new distance value must be less than old one");
// find new place for x
// i starts at old location of x and moves up tree
int i = location[x.vertex];
while (i != 1 && ((Comparable) x.weight)
.compareTo(heap[i/2].weight) < 0)
{// cannot put x in heap[i]
heap[i] = heap[i/2]; // move element down
location[heap[i].vertex] = i;
i /= 2; // move to parent
}
heap[i] = x;
location[x.vertex] = i;
}
}
The code for Prim's method now takes the form
given below (this code is commented out in the file Graph.java).
public class PrimWithMinHeap
{
/** find a min cost spanning tree using Prim's method
* @return false iff the weighted undirected graph is not connected
* @param t[0:n-2] has the min cost tree edges when done */
public boolean prim(WeightedEdge [] t)
{
verifyWeightedUndirected("prim");
int n = vertices();
boolean [] selected = new boolean [n + 1];
// selected[i] is true iff vertex i already in spanning tree
WeightedEdgeNode [] nearNbr = new WeightedEdgeNode [n + 1];
// nearNbr[i].vertex is nearest spanning tree neighbor of vertex i
// nearNbr[i].weight is distance to this nearest neighbor
// start with vertex 1 in the spanning tree
// initialize nearNbr and modified min heap of candidates
selected[1] = true;
ModifiedMinHeap h = new ModifiedMinHeap (n);
Iterator iv = iterator(1); // vertices adjacent to vertex 1
while (iv.hasNext())
{
WeightedEdgeNode we = (WeightedEdgeNode) iv.next();
nearNbr[we.vertex] = new WeightedEdgeNode(1, we.weight);
h.put(we);
}
// select n-1 edges for spanning tree
for (int i = 0; i < n - 1; i++)
{
// get nearest unselected vertex
WeightedEdgeNode we = h.removeMin();
if (we == null)
// no unselected neighbor remains
return false;
// select we.vertex
t[i] = new WeightedEdge(we.vertex, nearNbr[we.vertex].vertex,
we.weight);
selected[we.vertex] = true;
// update distances
iv = iterator(we.vertex);
while (iv.hasNext())
{
WeightedEdgeNode w = (WeightedEdgeNode) iv.next();
if (!selected[w.vertex])
{
if (nearNbr[w.vertex] == null)
{// w.vertex not in min heap
nearNbr[w.vertex] = new WeightedEdgeNode(we.vertex, w.weight);
h.put(w);
}
else
// w.vertex is in the min heap
if (((Comparable) nearNbr[w.vertex].weight)
.compareTo(w.weight) > 0)
{// found a closer neighbor
nearNbr[w.vertex].weight = w.weight;
nearNbr[w.vertex].vertex = we.vertex;
h.decreaseWeight(w);
}
}
}
}
// spanning tree found
return true;
}
}
When we use a chain as is done in Program 18.3, we get the implementation
shown below (this code is in the file Graph.java).
/** find a min cost spanning tree using Prim's method
* @return false iff the weighted undirected graph is not connected
* @param t[0:n-2] has the min cost tree edges when done */
public boolean prim(WeightedEdge [] t)
{
verifyWeightedUndirected("prim");
int n = vertices();
boolean [] selected = new boolean [n + 1];
// selected[i] is true iff vertex i already in spanning tree
WeightedEdgeNode [] nearNbr = new WeightedEdgeNode [n + 1];
// nearNbr[i].vertex is nearest spanning tree neighbor of vertex i
// nearNbr[i].weight is distance to this nearest neighbor
// start with vertex 1 in the spanning tree
// initialize nearNbr and list of unselected adjacent vertices
selected[1] = true;
GraphChain l = new GraphChain(); // list of unselected adjacent vertices
Iterator iv = iterator(1); // vertices adjacent to vertex 1
while (iv.hasNext())
{
WeightedEdgeNode we = (WeightedEdgeNode) iv.next();
nearNbr[we.vertex] = new WeightedEdgeNode(1, we.weight);
l.add(0, new EdgeNode(we.vertex));
}
// include remaining vertices into the spanning tree using Prim's method
int i = 0; // number of edges in spanning tree
while (!l.isEmpty())
{// there is an adjacent unselected vertex
// find adjacent unselected vertex v with least edge cost
Iterator il = l.iterator();
int v = ((EdgeNode) il.next()).vertex;
while (il.hasNext())
{
int w = ((EdgeNode) il.next()).vertex;
if (((Comparable) nearNbr[w].weight)
.compareTo(nearNbr[v].weight) < 0)
v = w;
}
// select vertex v and associated edge
t[i++] = new WeightedEdge(v, nearNbr[v].vertex, nearNbr[v].weight);
selected[v] = true;
// delete v from l and update nearNbr
l.removeElement(v);
// update distances
iv = iterator(v);
while (iv.hasNext())
{
WeightedEdgeNode w = (WeightedEdgeNode) iv.next();
if (!selected[w.vertex])
{
if (nearNbr[w.vertex] == null)
{// w.vertex not in min heap
nearNbr[w.vertex] = new WeightedEdgeNode(v, w.weight);
l.add(0, new EdgeNode(w.vertex));
}
else
// w.vertex is in l
if (((Comparable) nearNbr[w.vertex].weight)
.compareTo(w.weight) > 0)
{// found a closer neighbor
nearNbr[w.vertex].weight = w.weight;
nearNbr[w.vertex].vertex = v;
}
}
}
}
// see if spanning tree was found
if (i == n - 1)
return true;
else
return false;
}