Algorithm behind clustering, Prims Algorithm

Clustering

Cluster analysis, often known as clustering, is the process of grouping a set of items so that those in the same group are more similar than those in other groups. It is an unsupervised learning method, which means the algorithm receives no supervision and works with an unlabeled dataset.

And Using Prims we can get Shortest path between 2 points.

Since, Prims Algorithm uses Graph Data structure so let’s understand graph first.

Graph

A graph is a data structure consisting of nodes and edges that is non-linear. The nodes are also known as vertices, while the edges are lines or arcs that connect any two nodes in the graph. A graph is made up of a finite number of vertices (or nodes) and a set of Edges that connect them.

Now that we know what Graph is, let’s understand what is Minimum Spanning Tree (MST).

MINIMUM SPANNING TREE-

A minimum spanning tree is one in which the tree’s edge lengths (or “weights”) are maintained to a bare minimum. One path connects any two vertices in a tree.

The properties of MST are as follows-

· Contains all the original graph’s vertices.

· Reaches out to all vertices.

· Is acyclic in nature. In other words, there are no nodes in the graph that loop back to themselves.

· Possible multiplicity- Each spanning tree has n 1 edges if there are n vertices in the graph.

. uniqueness- There will be only one, unique minimum spanning tree if each edge has a different weight.

PRIMS ALGORITHM-

Prim’s algorithm is a greedy technique for finding the shortest path between two points in a graph. Prim’s method finds the subset of edges that includes every vertex in the graph and reduces the sum of the edge weights.

WORKING-

Prim’s algorithm begins with a single node and proceeds to all nearby nodes, studying all linked edges along the way. Edges with the minimum weights that didn’t generate any graph cycles were picked. Prim’s algorithm is a greedy method that starts with one vertex and adds the fewest weight edges until the goal is reached. The following are the stages to implementing Prim’s algorithm. -

• First, we must initialize an MST with the randomly chosen point.
• Now we must locate all of the edges that link the tree from the previous phase to the new vertices. Choose the shortest edge from the discovered edges and add it to the tree.
• Repeat step 2 until the MST is formed.

APPLICATION-

• Prim’s algorithm is used in network designing.
• It’s possible to create network cycles with it.
• It’s also good for laying down electrical wires.

PSEUDO CODE

Adjacency matrix, linear searching →O(|V|2)

Adjacency list and binary heap →O(|E| log |V|)

Adjacency list and Fibonacci heap →O(|E|+ |V| log |V|)

#include <stdio.h>
#include <limits.h>
#define vertices 5 /*Define the number of vertices in the graph*/
/* create minimum_key() method for finding the vertex that has minimum key-value and that is not added in MST yet */
int minimum_key(int k[], int mst[])
{
int minimum = INT_MAX, min,i;
/*iterate over all vertices to find the vertex with minimum key-value*/
for (i = 0; i < vertices; i++)
if (mst[i] == 0 && k[i] < minimum )
minimum = k[i], min = i;
return min;
}
/* create prim() method for constructing and printing the MST.
The g[vertices][vertices] is an adjacency matrix that defines the graph for MST.*/
void prim(int g[vertices][vertices])
{
/* create array of size equal to total number of vertices for storing the MST*/
int parent[vertices];
/* create k[vertices] array for selecting an edge having minimum weight*/
int k[vertices];
int mst[vertices];
int i, count,edge,v; /*Here ‘v’ is the vertex*/
for (i = 0; i < vertices; i++)
{
k[i] = INT_MAX;
mst[i] = 0;
}
k[0] = 0; /*It select as first vertex*/
parent[0] = -1; /* set first value of parent[] array to -1 to make it root of MST*/
for (count = 0; count < vertices-1; count++)
{
/*select the vertex having minimum key and that is not added in the MST yet from the set of vertices*/
edge = minimum_key(k, mst);
mst[edge] = 1;
for (v = 0; v < vertices; v++)
{
if (g[edge][v] && mst[v] == 0 && g[edge][v] < k[v])
{
parent[v] = edge, k[v] = g[edge][v];
}
}
}
/*Print the constructed Minimum spanning tree*/
printf(“\n Edge \t Weight\n”);
for (i = 1; i < vertices; i++)
printf(“ %d <-> %d %d \n”, parent[i], i, g[i][parent[i]]);
}
int main()
{
int g[vertices][vertices] = {{0, 0, 3, 0, 0},
{0, 0, 10, 4, 0},
{3, 10, 0, 2, 6},
{0, 4, 2, 0, 1},
{0, 0, 6, 1, 0},
};
prim(g);
return 0;
}

With the above code we can see Prim’s Algorithm in Action.

Hope you enjoyed this blog and got to know more, Thank you.