Nannette Bibby - Computer Science - Miami Dade College
PRIM’S ALGORITHM
Suppose G is a set of points in a plane. The points in G are called vertices. The following algorithm, called Prim’s algorithm, can be used to form a “minimal connecting network” for G if the distances between all pairs of vertices are known.
1. Select any vertex of G and connect it to a vertex nearest to it.
2. Find an unconnected vertex that is closest to previously connected vertices, and connect it.
3. Repeat step 2 until all vertices are connected.
FACTS ABOUT CONNECTING NETWORKS
Two vertices are connected by an edge. If G contains n vertices, then:
1. The number of edges required to form a completely connected network for G is
n(n – 1)/2.
2. The number of edges required to form a minimal connected network for G is n – 1.
These facts are illustrated in the following table.
|
Number of vertices |
Number of edges for a complete connection |
Number of edges for a minimal connection |
|
3 |
3 |
2 |
|
4 |
6 |
3 |
|
10 |
45 |
9 |
|
25 |
300 |
24 |
|
50 |
1,225 |
49 |
ILLUSTRATIONS (n = 5)
Completely connected network (10 edges)
Minimally connected network (4 edges)
Connected network, not complete or minimal
Disconnected network
BULLET TRAINS
A bullet train, or high-speed train, is a train that can travel at very high speeds. A speed of 300 miles per hour has been recorded, but average speeds are approximately 150 miles per hour. Bullet trains have been used extensively in Japan since the 1960s and in Europe since the 1980s. There are no bullet train systems in the United States.
BULLET TRAINS IN FLORIDA?
In November 2000, Florida voters narrowly approved a proposal to construct a bullet train system in Florida. The proposal specifies that bullet trains will eventually connect Florida’s four largest cities: Miami, Tampa, Orlando, and Jacksonville (Jax). Distances between pairs of these cities are given in the following table.
|
|
Miami |
Tampa |
Orlando |
Jax |
|
Miami |
--- |
206 |
201 |
326 |
|
Tampa |
206 |
--- |
77 |
171 |
|
Orlando |
201 |
77 |
--- |
127 |
|
Jax |
326 |
171 |
127 |
--- |
CONNECTING THE FLORIDA BULLET TRAIN CITIES USING PRIM’S ALGORITHM
|
Step 1. Select a city (Miami) and connect it to the nearest city (Orlando) |
|
|
Step 2. Select a non-connected city (Tampa) and connect it to the nearest previously-connected city (Orlando) |
|
|
Step 3. Select the last non-connected city (Jax) and connect it to the nearest previously-connected city (Orlando) |
|
The resulting minimal
connected network of the cities has a total distance of 405 miles.
PROGRAMMING FOR A MINIMAL CONNECTED NETWORK
An alternative to Prim’s algorithm for obtaining a minimal connected network is to start with a complete connected network and remove an appropriate number of the longest edges. This method works well provided that no removal of an edge produces a disconnection. If the removal of an edge produces a disconnection, simply maintain that edge and proceed to the next longest.
For example, given 12 vertices, a complete connected network contains 66 edges while a minimal connecting network will contain 11 edges. If we start with a complete connected network, the 55 longest edges may be removed (maintaining any edge whose removal would produce a disconnection) to obtain a minimal connected network.
