Prims Algorithm
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Agenda
• Introduction to Greedy Programming
• Examples of Greedy Programming
• Graph Theory
• Prims minimal spanning tree
• prims Algorithm in Java - Implementation
• prims minimal spanning tree Codes in Python
• Prims algorithm time complexity
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Introduction to Greedy Programming
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Introduction to Greedy Programming
What is Greedy approach to Programming ?
• An approach to programming where the first solution to a given problem is taken up as the
correct solution
• It works in a step-by-step fashion finding the best solution locally
• The benefit of using the Greedy approach is that It gives the best solution locally
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Examples of Greedy Programming
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Examples of Greedy Programming
Examples
• Travelling Salesman Problem
• Prim's Minimal Spanning Tree Algorithm
• Kruskal's Minimal Spanning Tree Algorithm
• Dijkstra's Algorithm
• Graph – Vertex Cover
• Knapsack Problem
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Graph Theory
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Graph Theory
• Graphs
• Degree of Graph
• Cycle in a Graph
• Trees
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Graph Theory
• Types of Graph
1. Null Graph
2. Trivial Graph
3. Directed Graph
4. Undirected Graph
5. Complete Graph
6. Connected Graph
7. Disconnected Graph
8. Regular Graph
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Graph Theory
• Trees
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims minimal spanning tree
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims minimal spanning tree
Spanning Tree
• A tree is a graph of vertices and edges without a cycle
• A spanning tree has all vertices connected and is constructed from the graph, and a graph can have
multiple spanning trees
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims minimal spanning tree
Spanning Tree
• Example
A 4
B
5
6
3
F C
9 1 7
E D
2
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims minimal spanning tree
Minimal Spanning Tree
• A minimal spanning tree is a spanning tree whose sum of weights of edges is the minimum
• Algorithms to find minimal spanning tree is Prims and Kruskal's
• Example
A 4
B
5
6
3
F C
9 1
7
E D
2 DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims minimal spanning tree
Prim’s algorithm example with Solution
• Prims Algorithm Example
A 4
B
5
6
3
F 9 C
1 7
E D
2
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims minimal spanning tree
Prim’s Algorithm Steps
1. Visited vertices = {0}
2. Visited edges = null
3. For all the vertices from 1 to V
find minimum edge between u in visited vertex and v in unvisited vertex
add v to visited vertices
add edge to spanning tree
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims minimal spanning tree
Minimal Spanning Tree
• Kruskal’s Algorithm Example
A 4
B
5
6
3
F 9 C
1 7
E D
2
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims minimal spanning tree
Which is better Prims or Kruskal's method of finding Spanning Tree?
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims minimal spanning tree
Prims Algorithm – Adjacency Matrix
A 4
B
5
6
3
F 9 C
1 7
E D
2
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims algorithm in Java -
implementation
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims minimal spanning tree Codes-
implementation in python
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims Algorithm Time Complexity
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Prims Algorithm Time Complexity
• Time complexity of Prims algorithm is V2(adjacency matrix) or O ( ( V + E ) l o g V ) (min heap) or
O(E log V) (fibonacci heap)
Where,
• V is no of vertices in Given Graph
• E is no of edges in Given Graph
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Summary
We discussed
• Greedy approach to programming
• Spanning tree, Minimal spanning tree
• How to find minimal spanning tree using Prim’s and Kruskal’s method?
• Its implementation in Java and Python.
DO NOT WRITE ANYTHING
HERE. LEAVE THIS SPACE FOR
WEBCAM
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Thank You
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
