### 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:

- Create distance array and assign INFINITY for vertex
- Create parent vertex array
- Create visited boolean array
- Take any random vertex for example v0
- Set
`distance[v0]=0`

- Set
`parent [v0] = -1 or null`

based parent data type - Now Iterate from V0 to Vn-1
- Take vertex u which has smaller distance in distance array and not visited yet
- Set visited[u] = true
- Iterate all adjacent vertices(v) of vertex u
- If
`visited[v] = false and distance[v] < graph[u][v]`

then`distance[v] = graph[u][v]`

`parent[v] = u`

- If

Latest Source Code:

Github: PrimMinimumSpanningTree.java

**Output:**

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