**1 Answer**

0

1.7kviews

Draw the minimum cost spanning tree using Kruskals algorithm. Also find its cost with all intermediate steps

0

12views

written 7.9 years ago by |

A minimum spanning tree can be defined as a spanning tree with weight less than or equal to the weight of every other spanning tree.

Let us find the minimum spanning tree for the given graph.

**Step 1: Remove all loops**

Here as no loops are present, we skip this step.

**Step 2: Remove all Parallel edges(i.e edges having multiple values)**

If so eliminate the edge with highest value and keep the one with least value intact. Here since such edges are not present, we skip this step.

**Step 3: Sort the edges according to minimum weights.**

Edge | Value |
---|---|

A-D | 1 |

E-F | 2 |

C-E | 3 |

E-D | 4 |

C-D | 5 |

D-F | 5 |

A-C | 6 |

A-B | 7 |

C-B | 8 |

**Step 4: Construct minimum spanning tree.**

Here we go from top to bottom of the above table by joining the given edges. An edge is discarded is it results in a cycle formation.

ADD COMMENT
EDIT

Please log in to add an answer.