A spanning tree of an undirected connected graph is its connected acyclic subgraph (i.e., a tree) that contains all the vertices of the graph. If such a graph has weights assigned to its edges, a minimum spanning tree is its spanning tree of the smallest weight, where the weight of a tree is defined as the sum of the weights on all its edges. The minimum spanning tree problem is the problem of finding a minimum spanning tree for a given weighted connected graph.

**Prim’s Algorithm**

The following problem arises
naturally in many practical situations: given ** n** points, connect them in the cheapest possible
way so that there will be a path between every pair of points. It has direct
applications to the design of all kinds of networks— including communication,
computer, transportation, and electrical—by providing the cheapest way to
achieve connectivity. It identifies clusters of points in data sets. It has
been used for classification purposes in archeology, biology, sociology, and
other sciences. It is also helpful for constructing approximate solutions to
more difficult problems such the traveling salesman problem (see Section 12.3).

We can represent the points
given by vertices of a graph, possible connections by the graph’s edges, and
the connection costs by the edge weights. Then the question can be posed as the
minimum spanning tree problem, defined formally as follows.

**DEFINITION
**A** ***spanning tree*** **of an undirected connected
graph is its connected** **acyclic subgraph (i.e., a tree) that contains
all the vertices of the graph. If such a graph has weights assigned to its
edges, a ** minimum spanning tree** is its spanning tree of the smallest
weight, where the

Figure 9.2 presents a simple
example illustrating these notions.

If we were to try
constructing a minimum spanning tree by exhaustive search, we would face two
serious obstacles. First, the number of spanning trees grows exponentially with
the graph size (at least for dense graphs). Second, generating all spanning
trees for a given graph is not easy; in fact, it is more difficult than finding
a *minimum* spanning tree for a
weighted graph by using one of several efficient algorithms available for this
problem. In this section, we outline *Prim’s*** algorithm**, which goes
back to at least 1957

Prim’s algorithm constructs a
minimum spanning tree through a sequence of expanding subtrees. The initial
subtree in such a sequence consists of a single vertex selected arbitrarily
from the set ** V** of the graph’s vertices. On
each iteration, the algorithm expands the current tree in the greedy manner by
simply attaching to it the nearest vertex not in that tree. (By the nearest
vertex, we mean a vertex not in the tree connected to a vertex in the tree by
an edge of the smallest weight. Ties can be broken arbitrarily.) The algorithm
stops after all the graph’s vertices have been included in the tree being
constructed. Since the algorithm expands a tree by exactly one vertex on each
of its iterations, the total number of such iterations is

Here is pseudocode of this
algorithm.

**ALGORITHM** *Prim(**G)*

//Prim’s algorithm for
constructing a minimum spanning tree //Input: A weighted connected graph ** G** =

//Output:
*E***_{T}** , the set of edges composing
a minimum spanning tree of

*E*_{T}** **←

**for ***i*** **←** **1** to **|*V*** **| −** **1** do**

find a
minimum-weight edge *e*^{∗} = *(v*^{∗}*, u*^{∗}** )** among
all the edges

*V*_{T}** **←

**return ***E*_{T}

The nature of Prim’s
algorithm makes it necessary to provide each vertex not in the current tree
with the information about the shortest edge connecting the vertex to a tree
vertex. We can provide such information by attaching two labels to a vertex:
the name of the nearest tree vertex and the length (the weight) of the
corresponding edge. Vertices that are not adjacent to any of the tree vertices
can be given the ∞ label indicating their
“infinite” distance to the tree vertices and a null label for the name of the
nearest tree vertex. (Alternatively, we can split the vertices that are not in
the tree into two sets, the “fringe” and the “unseen.” The fringe contains only
the vertices that are not in the tree but are adjacent to at least one tree
vertex. These are the candidates from which the next tree vertex is selected.
The unseen vertices are all the other vertices of the graph, called “unseen”
because they are yet to be affected by the algorithm.) With such labels,
finding the next vertex to be added to the current tree ** T** =

After we have identified a
vertex *u*^{∗} to be added to the tree, we need to perform
two operations:

Move *u*^{∗} from the set ** V** −

For each remaining vertex ** u** in

Figure 9.3 demonstrates the
application of Prim’s algorithm to a specific graph. Does Prim’s algorithm
always yield a minimum spanning tree? The answer to this question is yes. Let
us prove by induction that each of the subtrees *T*_{i}*,*

** i **=

In addition to edge *e***_{i}** =

How efficient is Prim’s
algorithm? The answer depends on the data structures chosen for the graph
itself and for the priority queue of the set ** V** −

We can also implement the
priority queue as a ** min-heap**. A min-heap is a mirror image of the heap structure
discussed in Section 6.4. (In fact, it can be im-plemented by constructing a
heap after negating all the key values given.) Namely, a min-heap is a complete
binary tree in which every element is less than or equal

to its children. All the
principal properties of heaps remain valid for min-heaps, with some obvious
modifications. For example, the root of a min-heap contains the smallest rather
than the largest element. Deletion of the smallest element from and insertion
of a new element into a min-heap of size ** n** are

If a graph is represented by
its adjacency lists and the priority queue is im-plemented as a min-heap, the
running time of the algorithm is in ** O(**|

because, in a connected
graph, |** V** | − 1 ≤ |

In the next section, you will
find another greedy algorithm for the minimum spanning tree problem, which is
“greedy” in a manner different from that of Prim’s algorithm.

**Exercises 9.1**

**
**Write pseudocode of the greedy algorithm for the change-making
problem, with an amount ** n** and coin denominations

**
**Design a greedy algorithm for the assignment problem (see Section
3.4). Does your greedy algorithm always yield an optimal solution?

*Job scheduling *Consider the problem of scheduling* **n** *jobs of known dura-tions *t*_{1}*, t*_{2}*, . . . , t***_{n}** for execution by a single processor. The jobs
can be executed in any order, one job at a time. You want to find a schedule
that minimizes the total time spent by all the jobs in the system. (The time
spent by one job in the system is the sum of the time spent by this job in
waiting plus the time spent on its execution.)

Design a greedy algorithm for
this problem. Does the greedy algorithm always yield an optimal solution?

**
***Compatible intervals *Given* **n** *open intervals* **(a*_{1}*, b*_{1}*), (a*_{2}*, b*_{2}*), . . . , (a*_{n}*, b*_{n}*)** *on* *the real line, each representing start and end times of some
activity requiring the same resource, the task is to find the largest number of
these intervals so that no two of them overlap. Investigate the three greedy
algorithms based on

**
**earliest start first.

**
**shortest duration first.

**
**earliest finish first.

For each of the three
algorithms, either prove that the algorithm always yields an optimal solution
or give a counterexample showing this not to be the case.

**
***Bridge crossing revisited *Consider the generalization
of the bridge crossing* *puzzle
(Problem 2 in Exercises 1.2) in which we have ** n >** 1 people whose bridge crossing times are

Design a greedy algorithm for
this problem and find how long it will take to cross the bridge by using this
algorithm. Does your algorithm yield a minimum crossing time for every instance
of the problem? If it does—prove it; if it does not—find an instance with the
smallest number of people for which this happens.

**
***Averaging down *There are* **n >** *1 identical vessels, one of them with* **W** *pints* *of water and the
others empty. You are allowed to perform the following operation: take two of
the vessels and split the total amount of water in them equally between them.
The object is to achieve a minimum amount of water in the vessel containing all
the water in the initial set up by a sequence of such operations. What is the
best way to do this?

**
***Rumor spreading *There are* **n** *people, each in possession of a different* *rumor. They want to share all the rumors with each other by
sending electronic messages. Assume that a sender includes all the rumors he or
she knows at the time the message is sent and that a message may only have one
addressee.

Design a greedy algorithm
that always yields the minimum number of messages they need to send to
guarantee that every one of them gets all the rumors.

**
***Bachet’s problem of weights *Find an optimal set of* **n** *weights* *{*w*_{1}*, w*_{2}*, . . . ,** **w***_{n}**}

** **weights can be put only on the free cup of the
scale. weights can be put on both cups of the scale.

**a. **Apply Prim’s algorithm to the following graph. Include in the
priority** **queue all the vertices not
already in the tree.

Apply Prim’s algorithm to the
following graph. Include in the priority queue only the fringe vertices (the
vertices not in the current tree which are adjacent to at least one tree
vertex).

**
**The notion of a minimum spanning tree is applicable to a connected
weighted graph. Do we have to check a graph’s connectivity before applying
Prim’s algorithm, or can the algorithm do it by itself?

**
**Does Prim’s algorithm always work correctly on graphs with negative
edge weights?

**
**Let ** T** be a minimum spanning tree
of graph

**
**How can one use Prim’s algorithm to find a spanning tree of a
connected graph with no weights on its edges? Is it a good algorithm for this
problem?

**
**Prove that any weighted connected graph with distinct weights has
exactly one minimum spanning tree.

Outline an efficient
algorithm for changing an element’s value in a min-heap. What is the time
efficiency of your algorithm?

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Greedy Technique : Prim’s Algorithm |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.