[go: up one dir, main page]
Scribd
Upload
21 views12 pages

Spanning Tree

The document discusses spanning trees and minimum spanning trees in graphs. It explains what spanning trees are, their properties, and applications. It then describes two algorithms - Kruskal's algorithm and Prim's algorithm - to find minimum spanning trees in weighted graphs.

Uploaded by

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

Spanning Tree

The document discusses spanning trees and minimum spanning trees in graphs. It explains what spanning trees are, their properties, and applications. It then describes two algorithms - Kruskal's algorithm and Prim's algorithm - to find minimum spanning trees in weighted graphs.

Uploaded by

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

Spanning Tree

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum
possible number of edges. Hence, a spanning tree does not have cycles and it cannot be
disconnected.

By this definition, we can draw a conclusion that every connected and undirected Graph
G has at least one spanning tree. A disconnected graph does not have any spanning tree,
as it cannot be spanned to all its vertices.

We now understand that one graph can have more than one spanning tree. Following are
a few properties of the spanning tree connected to graph G −

• A connected graph G can have more than one spanning tree.


• All possible spanning trees of graph G, have the same number of edges and
vertices.
• The spanning tree does not have any cycle (loops).
• Removing one edge from the spanning tree will make the graph disconnected, i.e.
the spanning tree is minimally connected.
• Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning
tree is maximally acyclic.

Application of Spanning Tree


• Civil Network Planning
• Computer Network Routing Protocol
• Cluster Analysis
Minimum Spanning Tree (MST)

In a weighted graph, a minimum spanning tree is a spanning tree that has minimum
weight than all other spanning trees of the same graph. In real-world situations, this weight
can be measured as distance, congestion, traffic load or any arbitrary value denoted to
the edges.

Minimum Spanning-Tree Algorithm


• Kruskal's Algorithm
• Prim's Algorithm

Introduction to Kruskal’s Algorithm:


In Kruskal’s algorithm, sort all edges of the given graph in increasing order. Then it
keeps on adding new edges and nodes in the MST if the newly added edge does not
form a cycle. It picks the minimum weighted edge at first and the maximum weighted
edge at last. Thus we can say that it makes a locally optimal choice in each step in order
to find the optimal solution.

How to find MST using Kruskal’s algorithm?


Below are the steps for finding MST using Kruskal’s algorithm:
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so
far. If the cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

The graph contains 9 vertices and 14 edges. So, the minimum spanning tree formed
will be having (9 – 1) = 8 edges.
Step 1: Pick edge 7-6. No cycle is formed, include it.

Step 2: Pick edge 8-2. No cycle is formed, include it.


Step 3: Pick edge 6-5. No cycle is formed, include it.

Step 4: Pick edge 0-1. No cycle is formed, include it.

Step 5: Pick edge 2-5. No cycle is formed, include it.

Step 6: Pick edge 8-6. Since including this edge results in the cycle, discard it. Pick
edge 2-3: No cycle is formed, include it.
Step 7: Pick edge 7-8. Since including this edge results in the cycle, discard it. Pick
edge 0-7. No cycle is formed, include it.

Step 8: Pick edge 1-2. Since including this edge results in the cycle, discard it. Pick
edge 3-4. No cycle is formed, include it.

Advantages of Kruskal’s Algorithm


1. Kruskal’s algorithm is simple to implement and can be used in a variety of
scenarios, including the calculation of minimum spanning trees.
2. Kruskal’s algorithm maintains all the vertices in the graph in the optimal solution.
This helps to reduce the amount of backtracking required to solve the problem,
making it ideal for situations where a large amount of computation is required or
the solution must be determined quickly.
3. Kruskal’s algorithm is efficient and reliable when implemented correctly, which
makes it a popular choice for real-world applications.

Disadvantages of Kruskal’s Algorithm


1. It is not guaranteed to converge to a local minimum, whereas it is with Prim’s
algorithm.
2. It does not produce the same number of possible paths as the other algorithms.
3. It requires a quadratic number of function evaluations.

Introduction to Prim’s algorithm:


Prim’s algorithm is also a Greedy algorithm. This algorithm always starts with a single
node and moves through several adjacent nodes, in order to explore all of the connected
edges along the way.
The algorithm starts with an empty spanning tree. The idea is to maintain two sets of
vertices. The first set contains the vertices already included in the MST, and the other
set contains the vertices not yet included. At every step, it considers all the edges that
connect the two sets and picks the minimum weight edge from these edges. After
picking the edge, it moves the other endpoint of the edge to the set containing MST.
A group of edges that connects two sets of vertices in a graph is called cut in graph theory.
So, at every step of Prim’s algorithm, find a cut, pick the minimum weight edge from the
cut, and include this vertex in MST Set (the set that contains already included vertices).

How does Prim’s Algorithm Work?


The working of Prim’s algorithm can be described by using the following steps:

Step 1: Determine an arbitrary vertex as the starting vertex of the MST.


Step 2: Follow steps 3 to 5 till there are vertices that are not included in the MST
(known as fringe vertex).
Step 3: Find edges connecting any tree vertex with the fringe vertices.
Step 4: Find the minimum among these edges.
Step 5: Add the chosen edge to the MST if it does not form any cycle.
Step 6: Return the MST and exit.
Step 1: Firstly, we select an arbitrary vertex that acts as the starting vertex of the
Minimum Spanning Tree. Here we have selected vertex 0 as the starting vertex.

Step 2: All the edges connecting the incomplete MST and other vertices are the edges
{0, 1} and {0, 7}. Between these two the edge with minimum weight is {0, 1}. So include
the edge and vertex 1 in the MST.
Step 3: The edges connecting the incomplete MST to other vertices are {0, 7}, {1, 7}
and {1, 2}. Among these edges the minimum weight is 8 which is of the edges {0, 7} and
{1, 2}. Let us here include the edge {0, 7} and the vertex 7 in the MST. [We could have
also included edge {1, 2} and vertex 2 in the MST].

Step 4: The edges that connect the incomplete MST with the fringe vertices are {1, 2},
{7, 6} and {7, 8}. Add the edge {7, 6} and the vertex 6 in the MST as it has the least
weight (i.e., 1).
Step 5: The connecting edges now are {7, 8}, {1, 2}, {6, 8} and {6, 5}. Include edge {6,
5} and vertex 5 in the MST as the edge has the minimum weight (i.e., 2) among them.

Step 6: Among the current connecting edges, the edge {5, 2} has the minimum weight.
So include that edge and the vertex 2 in the MST.
Step 7: The connecting edges between the incomplete MST and the other edges are
{2, 8}, {2, 3}, {5, 3} and {5, 4}. The edge with minimum weight is edge {2, 8} which has
weight 2. So include this edge and the vertex 8 in the MST.

Step 8: See here that the edges {7, 8} and {2, 3} both have same weight which are
minimum. But 7 is already part of MST. So we will consider the edge {2, 3} and include
that edge and vertex 3 in the MST.
Step 9: Only the vertex 4 remains to be included. The minimum weighted edge from the
incomplete MST to 4 is {3, 4}.

The final structure of the MST is as follows and the weight of the edges of the MST is
(4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37.
Advantages:
1. Prim’s algorithm is guaranteed to find the MST in a connected, weighted graph.
2. It has a time complexity of O(E log V) using a binary heap or Fibonacci heap,
where E is the number of edges and V is the number of vertices.
3. It is a relatively simple algorithm to understand and implement compared to some
other MST algorithms.
Disadvantages:
1. Like Kruskal’s algorithm, Prim’s algorithm can be slow on dense graphs with many
edges, as it requires iterating over all edges at least once.
2. Prim’s algorithm relies on a priority queue, which can take up extra memory and
slow down the algorithm on very large graphs.
3. The choice of starting node can affect the MST output, which may not be desirable
in some applications.

Prim’s Algorithm Kruskal’s Algorithm

It starts to build the Minimum It starts to build the Minimum Spanning


Spanning Tree from any vertex in Tree from the vertex carrying minimum
the graph. weight in the graph.

It traverses one node more than one


It traverses one node only once.
time to get the minimum distance.
Prim’s Algorithm Kruskal’s Algorithm

Prim’s algorithm has a time


complexity of O(V2), V being the Kruskal’s algorithm’s time complexity is
number of vertices and can be O(E log V), V being the number of
improved up to O(E log V) using vertices.
Fibonacci heaps.

Kruskal’s algorithm can generate


Prim’s algorithm gives connected
forest(disconnected components) at any
component as well as it works only
instant as well as it can work on
on connected graph.
disconnected components

Prim’s algorithm runs faster in Kruskal’s algorithm runs faster in sparse


dense graphs. graphs.

It generates the minimum spanning It generates the minimum spanning tree


tree starting from the root vertex. starting from the least weighted edge.

Applications of prim’s algorithm are


Travelling Salesman Problem, Applications of Kruskal algorithm are
Network for roads and Rail tracks LAN connection, TV Network etc.
connecting all the cities etc.

Prim’s algorithm prefer list data Kruskal’s algorithm prefer heap data
structures. structures.

You might also like