Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Алгоритм Прима жадібний алгоритм побудови мінімального кістякового дерева зваженого зв язного неорієнтованого графу Побу

Алгоритм Прима

Алгоритм Прима

Алгоритм Прима — жадібний алгоритм побудови мінімального кістякового дерева зваженого зв'язного неорієнтованого графу.

Побудова починається з дерева, що містить в собі одну (довільну) вершину. Протягом роботи алгоритму дерево розростається, поки не охопить усі вершини початкового графу. На кожному кроці алгоритму до поточного дерева приєднується найлегше з ребер, що з'єднують вершину з побудованого дерева і вершину, що не належить дереву.

Алгоритм

  1. Ініціалізувати дерево з однією вершиною, довільно вибраною з графа.
  2. Збільшити дерево на одне ребро: із ребер, що з’єднують дерево з вершинами, які ще не в дереві, знайти ребро мінімальної ваги та додати його у дерево.
  3. Повторювати крок 2, доки всі вершини не будуть у дереві.

Приклад виконання

1.Початковий зважений граф. Числа біля ребер показують їх вагу, яку можна розглядати як відстань між вершинами.

image

2. За початкову довільно обирають вершину D. Кожна з вершин A, B, E і F з'єднана з D єдиним ребром. Вершина A — найближча до D, і вибирається як друга вершина разом з ребром AD.

image

3.Наступна вершина — найближча до будь-якої з обраних вершин D або A. B віддалена від D на 9 і від A — на 7. Відстань до E дорівнює 15, а до F — 6. F є найближчою вершиною, тому вона включається в дерево F разом з ребром DF.

image

4.Аналогічними кроками приходимо до такого дерева. У цьому разі є можливість вибрати або C, або E, або G. C віддалена від B на 8, E віддалена від B на 7, а G віддалена від F на 11. E — найближча вершина, тому обирають E і ребро BE.

image

5.Єдина вершина, що залишилася — G. Відстань від F до неї одно 11, від E — 9. E ближче, тому обирають вершину G і ребро EG.

image

6.Вибрано всі вершини, мінімальне кістякове дерево побудовано

image

Оцінка складності

Цей розділ потребує доповнення.

Див. також

Посилання

  • Рыбаков Г. (2005). Минимальные остовные деревья. Санкт-Петербургский государственный университет информационных технологий, механики и оптики; факультет информационных технологий и программирования; кафедра компьютерных технологий; дискретная математика: алгоритмы. Архів оригіналу за 8 липня 2013. Процитовано 31 серпня 2011.


image Це незавершена стаття про алгоритми.
Ви можете проєкту, виправивши або дописавши її.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Algoritm Prima zhadibnij algoritm pobudovi minimalnogo kistyakovogo dereva zvazhenogo zv yaznogo neoriyentovanogo grafu Pobudova pochinayetsya z dereva sho mistit v sobi odnu dovilnu vershinu Protyagom roboti algoritmu derevo rozrostayetsya poki ne ohopit usi vershini pochatkovogo grafu Na kozhnomu kroci algoritmu do potochnogo dereva priyednuyetsya najlegshe z reber sho z yednuyut vershinu z pobudovanogo dereva i vershinu sho ne nalezhit derevu AlgoritmInicializuvati derevo z odniyeyu vershinoyu dovilno vibranoyu z grafa Zbilshiti derevo na odne rebro iz reber sho z yednuyut derevo z vershinami yaki she ne v derevi znajti rebro minimalnoyi vagi ta dodati jogo u derevo Povtoryuvati krok 2 doki vsi vershini ne budut u derevi Priklad vikonannya 1 Pochatkovij zvazhenij graf Chisla bilya reber pokazuyut yih vagu yaku mozhna rozglyadati yak vidstan mizh vershinami 2 Za pochatkovu dovilno obirayut vershinu D Kozhna z vershin A B E i F z yednana z D yedinim rebrom Vershina A najblizhcha do D i vibirayetsya yak druga vershina razom z rebrom AD 3 Nastupna vershina najblizhcha do bud yakoyi z obranih vershin D abo A B viddalena vid D na 9 i vid A na 7 Vidstan do E dorivnyuye 15 a do F 6 F ye najblizhchoyu vershinoyu tomu vona vklyuchayetsya v derevo F razom z rebrom DF 4 Analogichnimi krokami prihodimo do takogo dereva U comu razi ye mozhlivist vibrati abo C abo E abo G C viddalena vid B na 8 E viddalena vid B na 7 a G viddalena vid F na 11 E najblizhcha vershina tomu obirayut E i rebro BE 5 Yedina vershina sho zalishilasya G Vidstan vid F do neyi odno 11 vid E 9 E blizhche tomu obirayut vershinu G i rebro EG 6 Vibrano vsi vershini minimalne kistyakove derevo pobudovanoOcinka skladnostiCej rozdil potrebuye dopovnennya Div takozhAlgoritm KruskalaPosilannyaRybakov G 2005 Minimalnye ostovnye derevya Sankt Peterburgskij gosudarstvennyj universitet informacionnyh tehnologij mehaniki i optiki fakultet informacionnyh tehnologij i programmirovaniya kafedra kompyuternyh tehnologij diskretnaya matematika algoritmy Arhiv originalu za 8 lipnya 2013 Procitovano 31 serpnya 2011 Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi

Дата публікації:
Топ