Kruskal Algorithm In Hindi In Data Structure.

Anurag

5 years ago

हेलो दोस्तों, आज के इस ब्लॉग पोस्ट(Kruskal Algorithm In Hindi) में मैं आपको Kruskal algorithm के बारे में बताने जा रहा हूँ, जिसका उपयोग हम spanning tree find करने के लिए करते है |

इसमें हम optimal solutions को ढूंढ़ते है और उन्हें join करते जातें है और ध्यान रखते है कि कोई भी loop या cycle न बनने पाए. और प्रोसेस के बाद प्राप्त होने वाला tree spanning tree होता है |Kruskal Algorithm In Hindi|

Kruskal भी एक greedy algorithm है जिसका उद्देश्य optimal solution को दिए हुए problem में से अलग या find करना होता है | इस problem में हमें के undirected ग्राफ दिया जाता है और इसमें edges कि length दी गयी होती है|

How do you solve Kruskal’s algorithm?

Kruskal algorithm को step by step समझने के लिए निचे दिए गए procedure को ध्यान से देखे|

**kruskal algorithm In Hindi Procedure**

जैसा कि आप ऊपर दिए हुए चित्र में देख सकते है कि, हमें के undirected ग्राफ दिया गया है जिसका हमें spanning tree बनाना है |

Kruskal algorithm में हम सबसे पहले वो vertex के pair खोजते है जिसकी edge cost minimum हो, और यही प्रोसेस अंत तक चलता है, बस यहाँ पर हमें यह ध्यान रखना है कि कही पर भी साइकिल और loop formation नहीं होना चाहिए |

जैसा कि Fig a में दिखाया गया है कि DE कि cost सबसे छोटी है इसलिए सबसे पहले हम DE को join कर देते है |

Fig b में हम देखते है कि GH की cost minimum रहती है इसलिए हम उन्हें भी ज्वाइन कर देते है |

Fig c में हम देखते है कि DA कि cost सबसे कम है इसलिए हम उसे ज्वाइन कर देते है |

Fig d में हम देखते है कि FC कि cost कम है तो हम उन्हें भी ज्वाइन कर देते है |

Fig e में हम देखते है कि FB कि cost कम है तो हम उन्हें ज्वाइन कर देते है|

Fig f में हम देखते है कि BH कि cost कम है तो हम उन्हें ज्वाइन कर देते है |

Last वाले फिग में हम देखते है कि EG कि कॉस्ट मिनिमम है तो हम EG को ज्वाइन कर देते है |

इसके बाद जब minimum cost देख कर ज्वाइन करते है तो loop formation होने लगता है, इसलिए हम प्रोसेस को यहीं पर रोक देते है, last फिगर हमारा resultand spanning tree होता है |

यहाँ पर आपके दिमाग में एक question आ सकता है कि अगर 2 बराबर cost वाली एज है तो सबसे पहले कौन सी edge लेनी है?

वैसे यहाँ पर हमने edges को एक आर्डर में लिए है, पर आप कोई भी एज सेलेक्ट कर सकते है, इससे आपका स्पॅनिंग ट्री थोड़ा different होगा पर होगा वो भी एक spanning tree |

वैसे भी हम एक complete undirected ग्राफ से बहुत सारे spanning tree बना सकते है |
अगर हमारे ग्राफ में 3 वर्टेक्स है तो हम उससे ंपोn -2 स्पॅनिंग ट्री बना सकते है |

Prim’s Algorithm In Hindi In Data Structure. Prim’s Algorithm हिंदी में / How does Prim’s algorithm work?