Минималдуу каркас дарагы
Минималдуу каркас дарагы: Краскалдын алгоритми = кырларды иреттөө + DSU.
Маселе: бардык n шаарды минималдуу жалпы нарктагы жолдор менен байланыштыруу. Жооп ар дайым — n-1 кырдан турган дарак (циклдеги ашыкча кырды ыргытып салса болот), ал минималдуу каркас дарагы (MST) деп аталат.
Краскалдын алгоритми — иштээри далилденген ач көздүк:
1. Кырларды салмагы боюнча иреттөө.
2. Арзандан кымбатка карай жүрүү; кыр АР БАШКА компоненттерди бириктирсе — алуу.
3. «Компоненттер ар башкабы» дегенди мурунку деңгээлдеги DSU текшерет — мына ал кайда атат!
Татаалдыгы: иреттөөгө O(m log m), DSU дээрлик бекер.
Краскал. Киргизиңиз: 4 5, андан кийин кырлар: 1 2 1, 2 3 2, 3 4 5, 1 3 2, 2 4 4
Мисалда: кырлар салмагы боюнча өсүүдө 1, 2, 2, 4, 5. 1-2 алабыз (салмагы 1), 2-3 алабыз (салмагы 2), 1-3 кырын өткөрүп жиберебиз (мурдатан бир компонентте), 2-4 алабыз (салмагы 4). Жыйынтык: 1 + 2 + 4 = 7.
Ач көздүк эмнеге туура: графтын каалаган «кесүүсү» аркылуу өткөн эң арзан кыр сөзсүз кайсы бир MST ичинде жатат (эгер жок болсо — аны кошуңуз, циклде ошол эле кесүү аркылуу өткөн кымбатыраак кыр пайда болот, аны ыргытыңыз — начар болгон жок). Бул ач көздөр сабагындагы ошол эле алмаштыруу жүйөсү.
Примдин алгоритми да бар (даракты чокудан өстүрөбүз, Дейкстра сыяктуу) — ошол эле жыйынтык, башка стиль.
Тапшырма: программаны салмакты гана эмес, каркастын кырларынын өзүн да басып чыгаргыдай өзгөртүңүз.
Сабакты өттүм деп белгилеп, деңгээлдин башкы темасына — динамикалык программалоого өтүңүз.