Scribd
Upload
44 views4 pages

Experiment No. 4 Design and Analysis Spanning Tree: Solve Minimum Cost Spanning Tree Problem Using Greedy Method

The document describes algorithms for finding the minimum spanning tree of a weighted, undirected graph. It explains that a minimum spanning tree connects all vertices with the minimum total edge weight. Two algorithms are described: Prim's algorithm and Kruskal's algorithm. Prim's is greedy and maintains connected and unconnected vertex sets. Kruskal's sorts by edge weight and adds edges without cycles. The runtime of Kruskal's algorithm is analyzed as O(E log E) or O(E log V).

Uploaded by

dalip kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
44 views4 pages

Experiment No. 4 Design and Analysis Spanning Tree: Solve Minimum Cost Spanning Tree Problem Using Greedy Method

The document describes algorithms for finding the minimum spanning tree of a weighted, undirected graph. It explains that a minimum spanning tree connects all vertices with the minimum total edge weight. Two algorithms are described: Prim's algorithm and Kruskal's algorithm. Prim's is greedy and maintains connected and unconnected vertex sets. Kruskal's sorts by edge weight and adds edges without cycles. The runtime of Kruskal's algorithm is analyzed as O(E log E) or O(E log V).

Uploaded by

dalip kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Experiment no.

4
Solve minimum cost spanning tree problem using greedy method.

Design and Analysis Spanning Tree


A spanning tree is a subset of an undirected Graph that has all the
vertices connected by minimum number of edges.
If all the vertices are connected in a graph, then there exists at least one
spanning tree. In a graph, there may exist more than one spanning tree.
Properties

 A spanning tree does not have any cycle.


 Any vertex can be reached from any other vertex.
Minimum Spanning Tree
A Minimum Spanning Tree (MST) is a subset of edges of a connected
weighted undirected graph that connects all the vertices together with
the minimum possible total edge weight. To derive an MST, Prim’s
algorithm or Kruskal’s algorithm can be used.
As we have discussed, one graph may have more than one spanning
tree. If there are n number of vertices, the spanning tree should have n -
1 number of edges. In this context, if each edge of the graph is
associated with a weight and there exists more than one spanning tree,
we need to find the minimum spanning tree of the graph.

Moreover, if there exist any duplicate weighted edges, the graph may
have multiple minimum spanning tree.
In the above graph, we have shown a spanning tree though it’s not the
minimum spanning tree. The cost of this spanning tree is (5 + 7 + 3 + 3
+ 5 + 8 + 3 + 4) = 38.
We will use Prim’s algorithm to find the minimum spanning tree.

Prim’s Algorithm
 It is a greedy algorithm. It starts with an empty spanning tree. The idea is to
maintain two sets of vertices:
Contain vertices already included in MST.
Contain vertices not yet included.
At every step, it considers all the edges and picks the minimum weight edge.
After picking the edge, it moves the other endpoint of edge to set containing
MST.
Steps for finding MST using Prim's Algorithm:
Create MST set that keeps track of vertices already included in MST.
Assign key values to all vertices in the input graph. Initialize all key values as
INFINITE (∞). Assign key values like 0 for the first vertex so that it is picked
first.
While MST set doesn't include all vertices.
Pick vertex u which is not is MST set and has minimum key value. Include 'u'to
MST set.
Update the key value of all adjacent vertices of u. To update, iterate through
all adjacent vertices. For every adjacent vertex v, if the weight of edge u.v less
than the previous key value of v, update key value as a weight of u.v.
MST-PRIM (G, w, r)
1. for each u ∈ V [G]
2. do key [u] ← ∞
3. π [u] ← NIL
4. key [r] ← 0
5. Q ← V [G]
6. While Q ? ∅
7. do u ← EXTRACT - MIN (Q)
8. for each v ∈ Adj [u]
9. do if v ∈ Q and w (u, v) < key [v]
10. then π [v] ← u
11. key [v] ← w (u, v)

Kruskal's Algorithm:
An algorithm to construct a Minimum Spanning Tree for a connected weighted
graph. It is a Greedy Algorithm. The Greedy Choice is to put the smallest
weight edge that does not because a cycle in the MST constructed so far.

If the graph is not linked, then it finds a Minimum Spanning Tree.

Steps for finding MST using Kruskal's Algorithm:

1. Arrange the edge of G in order of increasing weight.


2. Starting only with the vertices of G and proceeding sequentially add
each edge which does not result in a cycle, until (n - 1) edges are used.
3. EXIT.

MST- KRUSKAL (G, w)


1. A ← ∅
2. for each vertex v ∈ V [G]
3. do MAKE - SET (v)
4. sort the edges of E into non decreasing order by weight w
5. for each edge (u, v) ∈ E, taken in non decreasing order by weight
6. do if FIND-SET (μ) ≠ if FIND-SET (v)
7. then A ← A ∪ {(u, v)}
8. UNION (u, v)
9. return A

Analysis: 
Where E is the number of edges in the graph and V is the number of vertices,
Kruskal's Algorithm can be shown to run in O (E log E) time, or simply, O (E log
V) time, all with simple data structures. These running times are equivalent
because:

o E is at most V2 and log V2= 2 x log V is O (log V).


o If we ignore isolated vertices, which will each their components of the
minimum spanning tree, V ≤ 2 E, so log V is O (log E).

Thus the total time is

1. O (E log E) = O (E log V).  

You might also like