Kruskal dhidi ya Prim
Katika sayansi ya kompyuta, algoriti za Prim na Kruskal ni algoriti ya uchoyo ambayo hupata mti wa kiwango cha chini kabisa unaozunguka kwa grafu iliyounganishwa isiyoelekezwa. Mti unaozunguka ni sehemu ndogo ya grafu hivi kwamba kila nodi ya grafu imeunganishwa na njia, ambayo ni mti. Kila mti unaotambaa una uzito, na kiwango cha chini zaidi cha uzito kinachowezekana cha miti yote inayozunguka ni mti wa chini kabisa unaozunguka (MST).
Mengi zaidi kuhusu Kanuni za Prim
Algoriti ilitengenezwa na mwanahisabati wa Kicheki Vojtěch Jarník mwaka wa 1930 na baadaye kwa kujitegemea na mwanasayansi wa kompyuta Robert C. Prim mwaka wa 1957. Iligunduliwa tena na Edsger Dijkstra mwaka wa 1959. Algorithm inaweza kutajwa katika hatua tatu muhimu;
Kwa kuzingatia grafu iliyounganishwa yenye nodi n na uzito wa kila ukingo, 1. Chagua nodi ya kiholela kutoka kwa grafu na uiongeze kwenye mti T (ambayo itakuwa nodi ya kwanza)
2. Fikiria uzani wa kila makali yaliyounganishwa na nodi kwenye mti na uchague kiwango cha chini. Ongeza makali na nodi kwenye mwisho mwingine wa mti T na uondoe makali kutoka kwa grafu. (Chagua yoyote ikiwa viwango vya chini viwili au zaidi vipo)
3. Rudia hatua ya 2, hadi kingo za n-1 ziongezwe kwenye mti.
Kwa njia hii, mti huanza na nodi moja ya kiholela na kupanuka kutoka nodi hiyo na kuendelea kwa kila mzunguko. Kwa hivyo, ili algorithm ifanye kazi vizuri, grafu inahitaji kuwa grafu iliyounganishwa. Aina ya msingi ya algoriti ya Prim ina uchangamano wa wakati wa O(V2).).
Mengi zaidi kuhusu Kanuni za Kruskal
Algoriti iliyotengenezwa na Joseph Kruskal ilionekana katika shughuli za Jumuiya ya Hisabati ya Marekani mwaka wa 1956. Algorithm ya Kruskal pia inaweza kuonyeshwa kwa hatua tatu rahisi.
Kwa kuzingatia grafu yenye nodi n na uzito mtawalia wa kila ukingo, 1. Chagua safu yenye uzito mdogo wa grafu nzima na uongeze kwenye mti na ufute kutoka kwa grafu.
2. Kati ya iliyobaki chagua makali yenye uzani mdogo, kwa njia ambayo haifanyi mzunguko. Ongeza makali kwenye mti na ufute kwenye grafu. (Chagua yoyote ikiwa viwango vya chini viwili au zaidi vipo)
3. Rudia mchakato katika hatua ya 2.
Kwa njia hii, kanuni ya algoriti huanza kwa makali yenye uzito mdogo na inaendelea kuchagua kila ukingo katika kila mzunguko. Kwa hiyo, katika algorithm grafu haifai kuunganishwa. Algorithm ya Kruskal ina ugumu wa wakati wa O(logV)
Kuna tofauti gani kati ya Kruskal's na Prim's Algorithm?
• Algoriti ya Prim huanzishwa kwa nodi, ilhali algoriti ya Kruskal huanzisha kwa ukingo.
• Algoriti za Prim huanzia nodi moja hadi nyingine huku algoriti ya Kruskal ikichagua kingo kwa njia ambayo nafasi ya ukingo haitokani na hatua ya mwisho.
• Katika algoriti ya prim, grafu lazima iwe grafu iliyounganishwa ilhali Kruskal inaweza kufanya kazi kwenye grafu zilizotenganishwa pia.
• Algoriti ya Prim ina uchangamano wa wakati wa O(V2), na uchangamano wa wakati wa Kruskal ni O(logV).
