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

Comparing Prim's With Kruskal's Algo

Prim's and Kruskal's algorithms are greedy algorithms used to find the minimum spanning tree (MST) of a weighted, connected, and undirected graph. Prim's algorithm finds the MST by growing a tree from an initial vertex, at each step adding the minimum weight edge that connects the growing tree to vertices not yet included. Kruskal's algorithm finds the MST by sorting all the edges by weight and building the MST by adding edges in order of increasing weight, skipping edges that would cause cycles. While Prim's runs in O(V^2) time and is better for dense graphs, Kruskal's runs faster in O(E log V) time and generally performs better, especially

Uploaded by

jenny luterio
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
113 views12 pages

Comparing Prim's With Kruskal's Algo

Prim's and Kruskal's algorithms are greedy algorithms used to find the minimum spanning tree (MST) of a weighted, connected, and undirected graph. Prim's algorithm finds the MST by growing a tree from an initial vertex, at each step adding the minimum weight edge that connects the growing tree to vertices not yet included. Kruskal's algorithm finds the MST by sorting all the edges by weight and building the MST by adding edges in order of increasing weight, skipping edges that would cause cycles. While Prim's runs in O(V^2) time and is better for dense graphs, Kruskal's runs faster in O(E log V) time and generally performs better, especially

Uploaded by

jenny luterio
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

COMPARING PRIM'S WITH

KRUSKAL'S ALGO

Luterio, Jenny P.
Villamor, Louise Faye
We have discussed -

Prim’s and Kruskal’s Algorithm are the famous greedy


algorithms.
They are used for finding the Minimum Spanning Tree
(MST) of a given graph.
To apply these algorithms, the given graph must be
weighted, connected and undirected.
Comparison Chart
Definition of Prim’s Algorithm

Prim’s algorithm is also a Greedy algorithm. It 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, 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 set of vertices in a graph is called cut in graph
theory. So, at every step of Prim’s algorithm, we find a cut (of two sets, one contains the
vertices already included in MST and other contains rest of the vertices), pick the
minimum weight edge from the cut and include this vertex to MST Set (the set that
contains already included vertices).
Below are the steps for finding MST using Prim’s algorithm

1.Create a set mstSet that keeps track of vertices already included in MST.
2. Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE.
Assign key value as 0 for the first vertex so that it is picked first.

3. While mstSet doesn’t include all vertices


Pick a vertex u which is not there in mstSet and has minimum key value.
Include u to mstSet.
Update the key value of all adjacent vertices of u. To update the key values, iterate
through all adjacent vertices. For every adjacent vertex v, if the weight of edge u-v is
less than the previous key value of v, update the key value as the weight of u-v
Definition of Kruskal’s Algorithm

Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is
a tree and connects all the vertices together. A single graph can have many different
spanning trees. A minimum spanning tree (MST) or minimum weight spanning tree for a
weighted, connected and undirected graph is a spanning tree with weight less than or equal
to the weight of every other spanning tree. The weight of a spanning tree is the sum of
weights given to each edge of the spanning tree.
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.
Key Differences Between Prim’s and Kruskal’s Algorithm

1.Prim’s algorithm works by choosing the adjacent vertices from the selected set of
vertices. In contrast, the Kruskal’s algorithm selects least weight edges instead of using
adjacency list, it organizes the edges by their weights.

2. The generation of minimum spanning tree in Prim’s algorithm is based on the


selection of graph vertices and it initiates with vertex whereas in Kruskal’s algorithm it
depends on the edges and initiates with an edge.

3. Prim’s algorithm always generates MST with connected components while this is
not the case in Kruskal’s algorithm where the MST may not have connected
components (i.e. Minimum spanning forest).
4. Kruskal’s algorithm works at a faster pace in the sparse graph. As against, Prim’s
algorithm performs better in the dense graph.

5. The time complexity of Prim’s algorithm is O(V2). Conversely, Kruskal’s algorithm runs
in O(log V) time.

6. In Prim’s algorithm, the adjacent vertices must be selected whereas Kruskal’s


algorithm does not have this type of restrictions on selection criteria.
Example of Prim’s Algorithm
Example of Kruskal’s Algorithm
Conclusion

The performance of the two algorithms could differ depending upon the certain
factors such as the number of vertices. Prim’s algorithm runs in O(V2) time and
works well in the massive graphs while Kruskal’s algorithm consumes O(log V) and
perform suitably with small graphs. Although, among both of the algorithm Kruskal’s
algorithm can generate better results.

You might also like