Algorithms in a Nutshell

(^170) | Chapter 6: Graph Algorithms
Consequences
For dense graphs, the priority queue can be implemented instead with a Fibonacci
heap. This improves the performance to O(E+VlogV), a significant speedup over
the binary heap implementation.
Analysis
The initialization phase of PRIM’SALGORITHMinserts each vertex into the
priority queue (implemented by a binary heap) for a total cost of O(VlogV). The
decreaseKeyoperation in PRIM’SALGORITHMrequires O(logq) performance,
whereqis the number of elements in the queue, which will always be less than
|V|. It can be called at most 2|E| times since each vertex is removed once from
the priority queue and each undirected edge in the graph is visited exactly twice.
Thus the total performance is O((V+2E)logn) or O((V+E)*logV).
Variations
KRUSKAL’SALGORITHMis an alternative to PRIM’SALGORITHM. It uses a
“disjoint-set” data structure to build up the minimum spanning tree by processing
all edges in the graph in order of weight, starting with the edge with smallest
weight and ending with the edge with largest weight. KRUSKAL’SALGORITHM
can be implemented in O(ElogE); with a sophisticated implementation of the
disjoint-set data structure, this can be reduced to O(ElogV). Details on this algo-
rithm can be found in (Cormen et al., 2001).
BinaryHeap pq(n);
vector inQueue(n, true);
for (int v = 0; v < n; v++) {
pq.insert(v, key[v]);
}
while (!pq.isEmpty( )) {
int u = pq.smallest( );
inQueue[u] = false;
// Process all neighbors of u to find if any edge beats best distance
for (VertexList::const_iterator ci = graph.begin(u);
ci != graph.end(u); ++ci) {
int v = ci->first;
if (inQueue[v]) {
int w = ci->second;
if (w < key[v]) {
pred[v] = u;
key[v] = w;
pq.decreaseKey(v, w);
}
}
}
}
}
Example 6-9. Prim’s Algorithm implementation with binary heap (continued)
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use