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