Discrete Structure

Class: FYMCA

 

Members: 

36. Onkar Kulkarni.

26. Kunal Ingale.

31. Rutik kadam .

25. Shantanu Inamdar.

 

 

Blog:

Prim’s Algorithm

 

Introduction:

Prim's Algorithm is a greedy algorithm that is used to find the minimum spanning tree from a graph Prim's algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized

 

Prim's algorithm starts with the single node and explores all the adjacent nodes with all the connecting edges at every step. The edges with the minimal weights causing no cycles in the graph got selected

 

History:

Prim's Algorithm was initially developed in 1930 by Czech mathematician Vojtěch Jarník.

Robert Clay Prim independently discovered it in 19571957, and in 19591959 it was rediscovered once more by Edsger Wybe Dijkstra.

For these reasons, it is also known as the DJP Algorithm, the Jarník Algorithm, or the Prim-Jarník Algorithm.

Prim's Algorithm is a greedy algorithm that is used to find the minimum spanning tree from a graph. Prim's algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized.

Steps of Prim’s Algorithm are as follows:

Step 1: Remove all the loops and parallel edges from the graph. While removing edges keep the one that has the least weightage.

Step 2: Now choose any node as the root node, any node can be a root node because in the spanning tree all the nodes of a graph are included and because it is connected then there must be at least one edge, which will join it to the rest of the tree.

Step 3: Now check outgoing edges from the root node and select the one with the least weight. After that check, outgoing edges from the newly connected node and select the one with the least weight, while doing this also consider the previous node and edges connected to that node which we have not selected previously. While doing this if you get two nodes of the same value you can select any one of those and continue.

Basically, Prim's algorithm treats the nodes as a single tree and keeps on adding new nodes to the spanning tree from the given graph. The spanning tree of any graph contains the same numbers of nodes as the graph and the number of edges would be (Number nodes -1 ). In the minimum Spanning tree, the total edge weight should be minimum.

Prim's algorithm is about finding the minimum weight spanning tree,

so it can be useable in the following  areas:

1] If you want to connect several cities using highways or rail networks, you can use these algos to find the minimum length of roads/rail tracks connecting all these cities.

2] Network Design - Suppose you have a business with several offices. You have to lease phone cables to connect all these offices. So you can make use of this algos to find out what is the minimum cost to connect all your offices with minimum use of phone cables.

3] Can be used to find the traveling salesman problem. This is a very famous problem using MST.

4] You want to apply a set of houses with - Electric Power, Telephone Lines, Sewage Lines.

5] Designing Local Area Networks

 

Prim's Algorithm Complexity:

The time complexity of Prim's algorithm is O(E log V).

 

Application of Prim's Algorithm :

Spanning tree - A spanning tree is the subgraph of an undirected connected graph.

Minimum Spanning tree - Minimum spanning tree can be defined as the spanning tree in which the sum of the weights of the edge is minimum. The weight of the spanning tree is the sum of the weights given to the edges of the spanning tree.

Prim's algorithm starts with the single node and explores all the adjacent nodes with all the connecting edges at every step. The edges with the minimal weights causing no cycles in the graph got selected.

Main applications of prim's algorithm are -

⦁        Prim's algorithm can be used in network designing.

⦁        It can be used to make network cycles.

⦁        It can also be used to lay down electrical wiring cables.

 

Example of prim's algorithm :

Now, let's see the working of prim's algorithm using an example. It will be easier to understand the prim's algorithm using an example.

Suppose, a weighted graph is -

 

Step 1 - First, we have to choose a vertex from the above graph. Let's choose B.

Step 2 - Now, we have to choose and add the shortest edge from vertex B. There are two edges from vertex B that are B to C with weight 6 and edge B to A with weight 1. Among the edges, the edge BA has the minimum weight. So, add it to the MST(Minimum Spaning Tree).

Step 3 - There are two edges from vertex A that are A to C with weight 6 and edge A to D with weight 5. Among the edges, the edge AD has the minimum weight. So, add it to the MST.

 

Just like above step we have to look for nearest low weight edge .We will have output like below: 

Here, no of vertices are 9 the no of edges will be v-1 i.e 8

 

Example:02

 

Prim's Algorithm pseudocode :

The pseudocode for prim's algorithm shows how we create two sets of vertices U and V-U. U contains the list of vertices that have been visited and V-U the list of vertices that haven't. One by one, we move vertices from set V-U to set U by connecting the least weight edge

 

Prim's vs Kruskal's Algorithm :

Kruskal's algorithm is another popular minimum spanning tree algorithm that uses a different logic to find the MST of a graph. Instead of starting from a vertex, Kruskal's algorithm sorts all the edges from low weight to high and keeps adding the lowest edges, ignoring those edges that create a cycle.