# Kruskal’s Algorithm

**Kruskal's** algorithm is a **greedy** technique used to find **minimum spanning tree** from the graph.It works on **edges** rather than on **vertices** in **connected weighted** graph.MST is obtained by finding global optimal choice.

**Technique**

**Mark**the**minimum weight edge**in the graph and**mark**the respective**vertices**.- Now,
**mark**the next minimum value in the graph. - If there are two or more
**edges**with same weight then select any**edge**at one time and then select others one by one. - We need to mark
**edges**according to the increasing**weight**of edges of different vertices. - Do not mark any edge on the graph which makes a
**cycle**. - Keep on repeating the process till
**MST**is obtained.

**Example**

Consider connected weighted graph in Fig 1.

- The
**minimum edge**weight on the graph is**1**.Edge**(Q,R)**and Edge**(S,W)**have same weight i.e**1**. - Choose any edge between them.
- Say we
**mark**Edge**(Q,R)**.(Fig 2) - Mark vertices
**Q and R**also.

- Now,
**mark**Edge**(S,W)**with weight**1**. **Mark**vertices**S and W**also.(Fig 3)

- Next min weight edge is
**2**. - Mark Edge
**(Q,P)**and vertex**P**.(Fig 4)

- The next min value in the graph is
**3**. - Mark Edge(
**R,S)**.(Fig 5)

- The next min value is
**4**. - Choose any edge between Edge
**(Q,T)**or Edge**(S,T)**. - Say we mark Edge
**(S,T)**with weight**4**. - The next value to be marked is
**4**but if we will mark Edge**(Q,T)**a**cycle SRQTS**will be formed. - So,do not mark this edge.
- We do not mark Edge
**(P,R)**with weight**5**,Edge**(T,W)**with weight**6**,Edge**(P,S)**with weight**13**for the same reason.(**Cycle formation**). - Now,mark Edge
**(W,X)**with weight**14**and mark vertex**X**.(Fig 6)

**Minimum spanning tree** is obtained as shown in Fig 7 and **cost** of minimum spanning tree is obtained by adding weights of all edges i.e **2+1+3+4+1+14=25**

## Comments

So empty here ... leave a comment!