# Prim’s algorithm

**Prim's** algorithm is a** greedy** algorithm as it finds the global** optimum** answer from collecting locally **optimum** choices.It finds the **minimum spanning tree** and works for **weighted,connected and undirected graph**.Minimum spanning tree is a graph is **edge weighted** graph whose weight is **smaller** than any other **spanning tree**.A minimum spanning tree is obtained by combining all local optimal choices to a global one.

**Technique**

- Put
**∞**as the**weight**at all**vertices**of the graph. - Write
**null**as the**parent**of each vertex. - Pick any
**vertex**from the graph. **Mark**it and replace the distance from**∞**to**0**.- Look for adjacent
**vertices**of**marked**vertex. - Replace
**∞**by given**weights**from the**marked**vertex to other vertices. - Replace parent
**null**by marked vertex name. - Choose minimum weight edge from the marked vertex.
**Mark**edge and another vertex .- Look for the
**adjacent**vertices. - If edge weight is smaller then replace the value as well by the
**parent**. - Now,look for all
**edges**from previous and newly marked vertex. - Choose the
**unvisited**vertex which is at**minimum**edge weight from marked vertices.(*Do not look again at marked vertices).* - Repeat the process till optimum solution is reached.
**Minimum spanning tree**is obtained as a result.

**Example**

Consider graph in Fig 1.

- Initially,put
**∞**followed by**null**and separated by comma at all**vertices**of graph.(Fig 2) -
**∞**is the weight and**null**is the parent

- Choose any
**vertex**from the graph. - Say
**T**is chosen. **Mark T**and replace weight by**0**.(Fig 3)- Add
**T**to the**set**i.e resulting sequence.

- Look for
**adjacent**vertices of T. **R,S,W**are the adjacent vertices.- Replace weights of
**R,S,W**by**12,4,6**respectively they are the distances from**T**. - Replace
**parent**of all**adjacent**vertices by**T**.(Fig 4)

- Choose the
**edge**from**T**which has**minimum**weight. **Edge(T,S)**is the shortest i.e**4**(compared to 12 and 6).- So mark the edge as well the vertex
**S**.(Fig 5). - Add
**S**to the set.

- Look for
**adjacent**neighbors of S. **P,R,W**are the adjacent vertices.- Replace value at
**P**by 1**3**and parent by**S**, as**13**is the edge weight from**S to P**. - Compare the edge weight betweenEdge(
**S, R**)and Edge(**T, R)**. **S to R**is**3**and**T to R**is**12**.3 is smaller than 12.- So,replace
**12**by**3**and**T**by**S**. - Compare weights between Edge (
**S , W)**and Edge (**T ,W)**. **S to W**is**1**and**T to W**is**6**.**1**is smaller so replace**6**,**T**by**1,S**.(Fig 6)

- Look for
**minimum**edge from**T and S**respectively. - 1 is minimum value(
**Edge(S,W)**). - Mark
**edge(S,W)**,vertex**W**and add them to the**set**.(Fig 7)

- Do not look for visited vertices again.
- Look for edges of
**T,S,W.** **3**is minimum edge value.**Mark edge**and vertex**R**.- Add
**R**to the set. - Look for
**unmarked**adjacent vertices of**R**. **P**is the unmarked vertex adjacent to**R**.- Replace
**13 by 5**and**S by R**as**5**is smaller than**13**.(Fig 8)

- The next
**minimum**value from edges of**T,S,W,R**is**5**. **Mark 5**and**P**.- Add
**P**to the set.(Fig 9)

- Replace value at
**Q**by**2**and parent by**P**.(Fig 10)

**Mark**2 and**vertex Q**.**Add Q**to the set.(Fig 11)

**Minimum spanning tree is **obtained and shown in Fig 12 and cost of minimum spanning tree is obtained by adding weights of all edges i.e.

**2+5+3+4+1 = 15**

** **

## Comments

So empty here ... leave a comment!