በክሩካል እና ፕሪም መካከል ያለው ልዩነት

2024 ደራሲ ደራሲ: Alex Aldridge | [email protected]. ለመጨረሻ ጊዜ የተሻሻለው: 2023-12-17 13:31

Kruskal vs Prim

በኮምፒዩተር ሳይንስ የPrim's እና Kruskal's አልጎሪዝም ለተገናኘ ክብደት ላለው ቀጥተኛ ያልሆነ ግራፍ የሚሆን ዝቅተኛ ስፋት ያለው ዛፍ የሚያገኝ ስግብግብ ስልተ ቀመር ናቸው። የተንጣለለ ዛፍ የግራፍ ንዑስ ግራፍ ሲሆን እያንዳንዱ የግራፍ መስቀለኛ መንገድ በመንገዱ የተገናኘ ሲሆን ይህም ዛፍ ነው. እያንዳንዱ የተንጣለለ ዛፍ ክብደት አለው እና የሁሉም የተንጣለለ ዛፎች ዝቅተኛው ክብደት/ዋጋ ዝቅተኛው የዛፍ ዛፍ (MST) ነው።

ተጨማሪ ስለPrim's Algorithm

አልጎሪዝም በ1930 በቼክ የሒሳብ ሊቅ Vojtěch Jarník እና በኋላ ራሱን ችሎ በኮምፒዩተር ሳይንቲስት ሮበርት ሲ ፕሪም በ1957 ተሰራ። በ 1959 በኤድስገር ዲጅክስታራ እንደገና ተገኘ። አልጎሪዝም በሦስት ቁልፍ ደረጃዎች ሊገለጽ ይችላል፡

የተገናኘው ግራፍ በ n ኖዶች እና የእያንዳንዱ ጠርዝ ክብደት፣

1። ከግራፉ ላይ የዘፈቀደ መስቀለኛ መንገድ ይምረጡ እና ወደ ዛፉ ቲ ያክሉት (ይህም የመጀመሪያው መስቀለኛ መንገድ ይሆናል)

2። በዛፉ ውስጥ ከሚገኙት አንጓዎች ጋር የተገናኘውን የእያንዳንዱን ጠርዝ ክብደት ግምት ውስጥ ያስገቡ እና ዝቅተኛውን ይምረጡ. በሌላኛው የዛፉ ጫፍ ጫፍ ላይ ጠርዙን እና መስቀለኛ መንገድን ይጨምሩ T እና ጠርዙን ከግራፉ ያስወግዱት. (ሁለት ወይም ከዚያ በላይ ዝቅተኛዎች ካሉ ማንኛውንም ይምረጡ)

3። ደረጃ 2ን ይድገሙት፣ n-1 ጠርዞች ወደ ዛፉ እስኪጨመሩ ድረስ።

በዚህ ዘዴ ዛፉ በነጠላ የዘፈቀደ መስቀለኛ መንገድ ይጀምርና ከዚያ መስቀለኛ መንገድ ጀምሮ በእያንዳንዱ ዑደት ይሰፋል። ስለዚህ፣ አልጎሪዝም በትክክል እንዲሰራ፣ ግራፉ የተገናኘ ግራፍ መሆን አለበት። የPrim's አልጎሪዝም መሰረታዊ ቅርፅ O(V^{2) የጊዜ ውስብስብነት አለው።}

ተጨማሪ ስለ ክሩስካል አልጎሪዝም

በጆሴፍ ክሩስካል የተሰራው አልጎሪዝም በ1956 በአሜሪካ የሂሳብ ማቲማቲካል ማህበር ሂደት ውስጥ ታየ።የክሩካል አልጎሪዝም በሶስት ቀላል ደረጃዎች ሊገለፅ ይችላል።

ግራፉ በ n ኖዶች እና የእያንዳንዱ ጠርዝ ክብደት ከተሰጠው፣

1። ከጠቅላላው ግራፍ በትንሹ ክብደት ያለውን ቅስት ይምረጡ እና ወደ ዛፉ ላይ ይጨምሩ እና ከግራፉ ይሰርዙ።

2። ከቀሪዎቹ ውስጥ አነስተኛውን የክብደት ጠርዝ ይምረጡ, ዑደት በማይፈጥር መንገድ. ጠርዙን ወደ ዛፉ ይጨምሩ እና ከግራፉ ላይ ይሰርዙ. (ሁለት ወይም ከዚያ በላይ ዝቅተኛዎች ካሉ ማንኛውንም ይምረጡ)

3። ሂደቱን በደረጃ 2 ይድገሙት።

በዚህ ዘዴ አልጎሪዝም የሚጀምረው በትንሹ ክብደት ባለው ጠርዝ እና በእያንዳንዱ ዑደት እያንዳንዱን ጠርዝ መምረጥ ይቀጥላል። ስለዚህ, በአልጎሪዝም ውስጥ ግራፉ መገናኘት አያስፈልግም. የክሩካል አልጎሪዝም የO(logV) የጊዜ ውስብስብነት አለው።

በKruskal's እና Prim's Algorithm መካከል ያለው ልዩነት ምንድን ነው?

• የፕሪም አልጎሪዝም የሚጀምረው በመስቀለኛ መንገድ ሲሆን የ Kruskal ስልተ ቀመር ግን በጠርዝ ይጀምራል።

• የፕሪም ስልተ ቀመሮች ከአንዱ መስቀለኛ መንገድ ወደ ሌላው ሲሄዱ የክሩካል አልጎሪዝም የጠርዙ አቀማመጥ በመጨረሻው ደረጃ ላይ በማይመሰረት መልኩ ጠርዞቹን ይመርጣል።

• በፕሪም አልጎሪዝም ግራፍ የተገናኘ ግራፍ መሆን አለበት ክሩስካል ግን በተቆራረጡ ግራፎች ላይም መስራት ይችላል።

• የፕሪም አልጎሪዝም የO(V^{22) የጊዜ ውስብስብነት አለው፣ እና የክሩካል የጊዜ ውስብስብነት O(logV) ነው።}