Крускал мен Прим
Информатикада Прим және Крускал алгоритмдері жалғанған өлшенген бағытталмаған график үшін ең аз таралу ағашын табатын ашкөз алгоритм болып табылады. Ағаш графигі - бұл графиктің әрбір түйіні жол арқылы жалғанатындай графтың ішкі сызбасы, ол ағаш. Әрбір созылатын ағаштың салмағы болады және барлық таралатын ағаштардың ең аз мүмкін салмағы/құны - ең аз таралатын ағаш (MST).
Прим алгоритмі туралы толығырақ
Алгоритмді 1930 жылы чех математигі Войтех Ярник, кейін 1957 жылы компьютер ғалымы Роберт Прим дербес әзірледі. Оны 1959 жылы Эдгер Дейкстра қайта ашты. Алгоритмді үш негізгі қадаммен көрсетуге болады;
n түйіні бар байланысты графикті және әр жиектің сәйкес салмағын ескере отырып, 1. Графиктен ерікті түйінді таңдап, оны T ағашына қосыңыз (ол бірінші түйін болады)
2. Ағаштағы түйіндерге қосылған әрбір жиектің салмағын қарастырып, минимумды таңдаңыз. Т ағашының екінші ұшына жиекті және түйінді қосып, графиктен жиекті алып тастаңыз. (Екі немесе одан да көп минимум бар болса, кез келгенін таңдаңыз)
3. 2-қадамды ағашқа n-1 жиектері қосылғанша қайталаңыз.
Бұл әдісте ағаш бір ерікті түйіннен басталады және әр цикл сайын сол түйіннен бастап кеңейеді. Демек, алгоритм дұрыс жұмыс істеуі үшін график байланысқан график болуы керек. Prim алгоритмінің негізгі пішінінің уақыт күрделілігі O(V2).
Крускаль алгоритмі туралы толығырақ
Джозеф Крускал әзірлеген алгоритм 1956 жылы Америка математикалық қоғамының еңбектерінде пайда болды. Крускал алгоритмін үш қарапайым қадаммен де көрсетуге болады.
n түйіні бар графикті және әр жиектің сәйкес салмағын ескере отырып, 1. Бүкіл графиктің салмағы ең аз доғаны таңдап, ағашқа қосыңыз және графиктен жойыңыз.
2. Қалғандардың ішінен ең аз салмақты жиекті циклды құрмайтындай етіп таңдаңыз. Шетін ағашқа қосып, графиктен жойыңыз. (Екі немесе одан да көп минимум бар болса, кез келгенін таңдаңыз)
3. 2-қадамдағы процесті қайталаңыз.
Бұл әдісте алгоритм ең аз салмақталған жиектен басталады және әр циклде әрбір жиекті таңдауды жалғастырады. Сондықтан алгоритмде графикті қосу қажет емес. Крускал алгоритмінің уақыт күрделілігі O(logV)
Крускаль мен Прим алгоритмінің айырмашылығы неде?
• Prim алгоритмі түйінмен инициализацияланады, ал Крускал алгоритмі жиекпен басталады.
• Prim алгоритмдері бір түйіннен екіншісіне таралады, ал Крускал алгоритмі жиектерді соңғы қадамға негізделмейтіндей етіп таңдайды.
• Прим алгоритмінде график жалғанған график болуы керек, ал Крускальдікі ажыратылған графиктерде де жұмыс істей алады.
• Прим алгоритмінің уақыт күрделілігі O(V2), ал Крускалдың уақыт күрделілігі – O(logV).
