prim

Prim – tai algoritmas, skirtas rasti minimalų jungųjį medį (MJM) svoriniam grafui. Jis veikia pradedant nuo bet kurios viršūnės ir paeiliui prideda mažiausią svorio briauną, jungiančią jau pasiektas viršūnes su naujomis.

Pagrindinė idėja:
1. Pradėk nuo bet kurios viršūnės.
2. Kiekviename žingsnyje rask mažiausią briauną, jungiančią medyje esančią viršūnę su nepriklausančia.
3. Pridėk tą briauną ir viršūnę.
4. Kartok, kol visos viršūnės prijungtos.

Pavyzdys
Grafas su viršūnėmis A, B, C, D:
- Briaunos: A–B (1), A–C (3), B–C (2), B–D (4), C–D (5).

Prim algoritmo veikimas:
1. Pradedam nuo A.
2. Mažiausia briauna iš A: A–B (1) → prijungiam B.
3. Dabar turim A, B. Mažiausia briauna į naują viršūnę: B–C (2) → prijungiam C.
4. Turim A, B, C. Mažiausia briauna į D: B–D (4) → prijungiam D.

Minimalus jungusis medis: A–B (1), B–C (2), B–D (4). Bendras svoris = 7.

Pritaikymas: Tinklo projektavimas, keliai, elektros tinklai.

Įrašas
Paaiškinimas	Prim – tai algoritmas, skirtas rasti minimalų jungųjį medį (MJM) svoriniam grafui. Jis veikia pradedant nuo bet kurios viršūnės ir paeiliui prideda mažiausią svorio briauną, jungiančią jau pasiektas viršūnes su naujomis. Pagrindinė idėja: 1. Pradėk nuo bet kurios viršūnės. 2. Kiekviename žingsnyje rask mažiausią briauną, jungiančią medyje esančią viršūnę su nepriklausančia. 3. Pridėk tą briauną ir viršūnę. 4. Kartok, kol visos viršūnės prijungtos. Pavyzdys Grafas su viršūnėmis A, B, C, D: - Briaunos: A–B (1), A–C (3), B–C (2), B–D (4), C–D (5). Prim algoritmo veikimas: 1. Pradedam nuo A. 2. Mažiausia briauna iš A: A–B (1) → prijungiam B. 3. Dabar turim A, B. Mažiausia briauna į naują viršūnę: B–C (2) → prijungiam C. 4. Turim A, B, C. Mažiausia briauna į D: B–D (4) → prijungiam D. Minimalus jungusis medis: A–B (1), B–C (2), B–D (4). Bendras svoris = 7. Pritaikymas: Tinklo projektavimas, keliai, elektros tinklai.
	Išsaugoti

Jūsų pataisymai bus išsiųsti moderatorių peržiūrai, jei informacija tikslesnė/taisyklingesnė
ji bus patalpinta vietoj esamos.