Prima algoritmı
Algoritm ideyası. Graf ushlariniń qálegeni saylanadı. Keyin bul ushtan shiqqan barlıq qırlardan eń arzan bahalisi saylanadı. Solay etip eki ushlı bir qırlı terekti payda etemiz. Sodan keyin bir ushi usi terekke tiyisli bolǵan barlıq qırlardan eń arzan bahalisi saylanadı. Bul qır yamasa qırlar, eger eń arzan bahalisi bir neshe bolsa, terekke qosıladı. Qırlardı qosıw procesi bunday qosıwlar cikl payda etilgenshe dawam etedi. Bunday terek qurıw procesi áste aqırın grafti barlıq ushlarin óz ishine aladı. Solay etip, graf qırlarınan shólkemlesken terek payda etemiz, terekke qalǵan ushlardan qálegenin qosılıwı cikl payda etedi. Ostov teregin qurıw procesin hám ayqın suwretin aldın keltirilgen mısalda kóremız.
11.3-súwret.
Birinshi etapda biz qálegen ushin tańlap alamız. Mısalı D ushin tańlaymiz. D uchinan eki DC hám DE qırlar shıǵıp, olardan eń arzan bahalisi DC qır boladı. Solay etip bir qır DC hám eki D hám C ushtan shólkemlesken terek payda etemiz.
Bul ushlardan DE, SB, SA, SE qırlar shıǵadı. Olardan mánisi boyınsha eń arzanı SA qır boladı jáne onı qurılǵan terekke qosıp DSA terek payda etemiz
11.4-súwret.
D
7
8 C
A
Sodan keyin bul terek ushlarinan shıǵıwshı qırlardan eń arzan bahalisin tańlawımız kerek. Bunday qırlar 6 bolıp olar: DE, CB, CE, AB, AE, AG. Mánisi boyınsha eń arzanı AB qırı boladı. Onı qurılǵan terekke qosıp D S A V terek payda etemiz.
1 1.5-súwret. D
B 7
5 8 C
A
Tap sonday qaǵıyda boyınsha keyingi basqıshta AG qır qosıladı hám taǵı terek payda etiledi.
1 1.6-súwret. D
B 7
A 5 8 C
6
G
Keyingi qádemde GF qır qosıladı hám 11.7-súwret kórinisindegi terek payda boladı
11.7-súwret.
D
B 7
A 5 8 C
6
G 8
F
Sonnan keyin bul terekke qosıw múmkin bolǵan qırlardı mánisi boyınsha saralap DE qırdı anıqlaymız jáne onı qosıp 11.8-súwret. kórinisindegi terekti payda etemiz.
1 1.8-súwret.
D
B 7 9
A 5 8 C E
6
G8
F
58. Kraskal algoritmin túsindirip beriń
|
