# Prim’s Minimum Spanning Tree

### Prim’s Minimum Spanning Tree

##### Spanning Tree – A tree that spans all the vertices of a connected and undirected graph .

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Spanning Tree Properties

• for graph G(V, E), it contains exact (V-1) edges
• Remove (E-V+1) edges
• Maximally acyclic – Means after adding an edge will be cycle
• Minimally connected – means removable of an edge from spinning tree it will give more than one components
• maximum possible spinning tree is V ^ (V-2)

Solution:

• It’s a greedy algorithm
• It can be implemented in various ways -like
• By priority queue {@link PrimMinimumSpanningTree}
• By fibonaci heap
• By Binary heap
• Here we’ll implement in simple way though its not optimised
##### How Prim’s works:
• Maintain two collections of vertices one that added to output and another that still not process.
• Take distance map for each vertex any add infinity for each vertices
• Take any random vertex and and assign distance to this is 0.
• Now iterate till all vertices not added to MST collection.
• And a vertices from distance map who has smallest distance and that vertex is not added in MST collection
• Process all adjacent vertices at are not added in MST collection and distance is lesser
• All these vertices update parent map and distance map
• Repeat this till all vertices not added to MST collection
##### Algorithm:
2. Create parent vertex array
3. Create visited boolean array
4. Take any random vertex for example v0
5. Set `distance[v0]=0`
6. Set `parent [v0] = -1 or null` based parent data type
7. Now Iterate from V0 to Vn-1
1. Take vertex u which has smaller distance in distance array and not visited yet
2. Set visited[u] = true
3. Iterate all adjacent vertices(v) of vertex u
1. If` visited[v] = false and distance[v] < graph[u][v] `then
1. `distance[v] = graph[u][v]`
2. `parent[v] = u`

Latest Source Code:
Github: PrimMinimumSpanningTree.java

Output:

``` Edge   Weight
0 - 1 -- 2
1 - 2 -- 3
0 - 3 -- 6
1 - 4 -- 5
```