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

Алгоритми пошуку графами та деревами
Переліки
Пов'язані теми

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

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

Алгоритм

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

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

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

Prim Algorithm 0

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

Prim Algorithm 1

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

Prim Algorithm 2

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

Prim Algorithm 4

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

Prim Algorithm 6

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

Prim Algorithm 7

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

Див. також

Посилання

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


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

Read other articles:

Ketua Dewan Federasi Rusia

Ketua Dewan Federasi Majelis Federal Federasi RusiaПредседатель Совета Федерации Федерального Собрания Российской ФедерацииPredsedatel' Soveta Federatsii Federal'nogo sobraniya Rossiyskoy FederatsiiPetahanaValentina Matviyenkosejak 21 September 2011Ditunjuk olehDewan FederasiMasa jabatanTidak ada batasan masa jabatanDibentuk13 Januari 1994; 30 tahun lalu (1994-01-13)Pejabat pertamaVladimir ShumeykoSitus webFederation ...

 

Kota Payakumbuh

Untuk nama kecamatan, lihat Payakumbuh, Lima Puluh Kota. Kota Payakumbuh PajacomboKotaTranskripsi bahasa daerah • Jawi Minangڤايوكومبواه • Alfabet MinangPayokumbuahDari atas, kiri ke kananː Kantor DPRD Kota Payakumbuh, Masjid Gadang Balai Nan Duo, Ngalau Indah Payakumbuh, Tugu di Jalan Soekarno-Hatta yang kini menjadi Tugu Adipura, Gunung Sago, Persimpangan jalan Tugu Adipura, dan persawahan. LambangJulukan: Kota KulinerKota GalamaiPetaKota Payaku...

 

Front Royal, Virginia

Town in Virginia, United StatesFront RoyalTownTown of Front RoyalAerial view of Front Royal SealNickname(s): Canoe Capital of Virginia, Fro Ro, The RoyalFront RoyalShow map of Shenandoah ValleyFront RoyalShow map of VirginiaFront RoyalShow map of the United StatesCoordinates: 38°56′N 78°12′W / 38.933°N 78.200°W / 38.933; -78.200CountryUnited StatesStateVirginiaCountyWarrenFounded1788Government • MayorLori A. CockrellArea[1] •...

Luiza Gega

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Desember 2022. Luiza GegaInformasi pribadiLahir5 November 1988 (umur 35)Dibër, AlbaniaTinggi159 m (521 ft 8 in)Berat45 kg (99 pon) (99 pon) OlahragaNegara AlbaniaOlahragaTrek dan lapanganLombaLari halang rintang 3000m Luiza Gega (...

 

Snuper

SnuperSnuper dalam acara penandatanganan di Lotte Mall, Gimpo, Oktober 2018.Kiri ke kanan: Taewoong, Suhyun, Sangil, Woosung, Sangho, dan SebinInformasi latar belakangAsalSeoul, Korea SelatanGenreK-popsynthpopdance-popballadTahun aktif2015 (2015)–sekarangLabelWidmay EntertainmentSitus websnuper.krAnggota Suhyun Sangil Taewoong Woosung Sangho Sebin Snuper (Hangul: 스누퍼; artinya lebih dari Super) adalah sebuah grup vokal laki-laki Korea Selatan bentukan Widmay Entertainment...

 

Marco Pappa

Nama ini menggunakan cara penamaan Spanyol: nama keluarga pertama atau paternalnya adalah Pappa dan nama keluarga kedua atau maternalnya adalah Ponce. Marco Pappa Pappa bersama Chicago Fire pada 2008Informasi pribadiNama lengkap Marco Pablo Pappa Ponce[1]Tanggal lahir 15 November 1987 (umur 36)[1]Tempat lahir Kota Guatemala, GuatemalaTinggi 1,78 m (5 ft 10 in)Posisi bermain GelandangKarier junior2004–2006 MunicipalKarier senior*Tahun Tim Tampil (Gol)...

Sha'ari Tadin

Singaporean politician In this Malay name, there is no surname or family name. The name Tadin is a patronymic, and the person should be referred to by their given name, Sha'ari. This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve...

 

Dieulafoy's lesion

Medical conditionDieulafoy's lesionOther namesExulceratio simplex DieulafoyBlood supply of stomachPronunciationDo-la-foy SpecialtyGastroenterologySymptomsHematemesis, melena, hematochezia, anemiaUsual onset52 years (average age)CausesAberrant submucosal arterioleDiagnostic methodUpper endoscopyTreatmentEndoscopic therapy with endoclip, argon plasma coagulation, electrocautery, epinephrine injection, etcPrognosis8% mortality[1]Frequency1.5% of gastrointestinal bleeding Dieulafoy's...

 

Vincentian

Vincentian (atau Vinsensian)kenapa tidak berpikir sendirimerupakan sebutan untuk kaum religius baik imam maupun bruder atau suster dan awam dalam Gereja Katolik yang tergabung dalam tarekat atau kongregasi atau serikat atau perkumpulan yang didirikan atau diinspirasikan oleh Santo Vincentius a Paulo. Di seluruh dunia terdapat kurang lebih empat ratusan tarekat atau kelompok awam baik dalam Gereja Katolik, Gereja Anglikan, maupun Gereja-gereja Kristen yang lain yang menyebut dirinya diinspiras...

Let's Talk About Love

Let's Talk About LoveAlbum studio karya Celine DionDirilis18 November 1997Direkam1997GenrePopDurasi74:35LabelColumbia, EpicProduserWalter Afanasieff, David Foster, Humberto Gatica, Corey Hart, James Horner, George Martin, Billy Pace, Tony Renis, Jim Steinman, Ric WakeKronologi Celine Dion Live à Paris(1996)Live à Paris1996 Let's Talk About Love(1997) S'il suffisait d'aimer(1998)S'il suffisait d'aimer1998 Let's Talk About Love merupakan sebuah album karya penyanyi pop berkebangsaan Kanad...

 

Pernod Ricard

French company that produces distilled beverages Pernod Ricard S.A.Company typePublic (Société Anonyme)Traded asEuronext Paris: RI CAC 40 ComponentISINFR0000120693 IndustryDrink industryFounded1975; 49 years ago (1975)FounderPaul RicardHeadquartersParis, FranceArea servedWorldwideKey peopleAlexandre Ricard (Chairman & Chief Executive Officer)[1]ProductsAlcoholic beveragesRevenue€8.824 billion (2021)Operating income3,265,000,000 Euro (2023) Net ...

 

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。 数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券（「壱」が大字） 弐千円日本銀行券（「弐」が大字） 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

Juan Candelaria

American politician Juan CandelariaMember of the Connecticut House of Representativesfrom the 95th districtIncumbentAssumed office January 7, 2003 Personal detailsBorn (1970-10-27) October 27, 1970 (age 53)Hatillo, Puerto Rico Juan R. Candelaria (born October 27, 1970) is an American Democratic politician. He is a member of the Connecticut House of Representatives from the 95th District, being first elected in 2002.[1][2] He is a member of the Appropriatio...

 

Chiaramonti

Chiaramonti Tzaramònte, Ciaramònti, ChjaramòntiKomuneComune di ChiaramontiLokasi Chiaramonti di Provinsi SassariNegaraItaliaWilayah SardiniaProvinsiSassari (SS)Pemerintahan • Wali kotaAlessandro UnaliLuas • Total98,61 km2 (38,07 sq mi)Ketinggian430 m (1,410 ft)Populasi (2016) • Total1,639[1]Zona waktuUTC+1 (CET) • Musim panas (DST)UTC+2 (CEST)Kode pos07030Kode area telepon079Situs webhttp://www.comune.chi...

 

التربية الكثيفة للحيوانات

زراعة عام أعمال تجارية زراعية علم الإنتاج النباتي حراجة زراعية علم الزراعة تربية الحيوان زراعة موسعة مزرعة نطاق حر زراعة آلية وزارة الزراعة زراعة مكثفة حيوان محاصيل زراعة عضوية زراعة معمرة زراعة بدون الحيوانات الزراعة المستدامة الجامعات زراعة حضرية تاريخ تاريخ الزراعة �...

Arktisk Kommando

Arktisk Kommando Logo des Arktisk Kommando Aufstellung 2012 Staat Danemark Königreich Dänemark Faroer Färöer Gronland Grönland Streitkräfte Dänische Streitkräfte Teilstreitkraft Heer, Marine, Luftwaffe Typ Kommando Stärke etwa 40 Mann Standort Nuuk Leitung Kommandeur Generalmajor Søren Andersen Das Arktisk Kommando („Arktisches Kommando“) ist ein Teil der dänischen Streitkräfte und untersteht dem gemeinsamen Verteidigungskommando. Inhaltsverzeichnis 1 Aufgaben ...

 

James, son of Alphaeus

One of the Twelve Apostles of Jesus Christ SaintJames the LesserSt James the Minor by Peter Paul Rubens (1613)Apostle and MartyrBornc. 1st century ADGalilee, Judaea, Roman EmpireDiedc. 62 ADJerusalem, Judaea, Roman Empire or Aegyptus, Roman EmpireVenerated inAll Christian denominations that venerate saintsFeast1 May (Anglican Communion),May 3 (Roman Catholic Church), 9 October (Eastern Orthodox Church)AttributesCarpenter's saw; fuller's clubPatronageApothecaries; druggists; dying people;...

 

Augustins de l'Assomption

Pour les articles homonymes, voir Assomption (homonymie) et AA. Augustins de l'Assomption(Assomptionnistes) Que vienne ton Règne (Mt 6,10). À cause de l'amour de notre Seigneur Jésus-Christ Ordre de droit pontifical Approbation diocésaine 1er mai 1857 Approbation pontificale 26 novembre 1864par Pie IX Type congrégation cléricale Spiritualité augustinienne et alzonienne Règle règle de saint Augustin Structure et histoire Fondation 25 décembre 1845 Fondateur Emmanuel d'Alzon Abrévia...

Iron Man (serie animata 2010)

Questa voce sull'argomento anime e manga è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Iron Manアイアンマン(Aian Man) Serie TV animeRegiaTakeshi Koike SceneggiaturaWarren Ellis, Toshiki Inoue Char. designTakahiro Umehara MusicheActivation (sigla iniziale), The Fight Never Ends (sigla finale) StudioMadhouse ReteAnimax 1ª TV1º ottobre – 17 dicembr...

 

Gil Dobie

American football player and coach (1878–1948) Gil DobieDobie in 1937Biographical detailsBorn(1878-01-21)January 21, 1878Hastings, Minnesota, U.S.DiedDecember 23, 1948(1948-12-23) (aged 70)Hartford, Connecticut, U.S.Playing career1900–1902Minnesota Position(s)End, quarterbackCoaching career (HC unless noted)Football1906–1907North Dakota Agricultural1908–1916Washington1917–1919Navy1920–1935Cornell1936–1938Boston CollegeBasketball1906–1908North Dakota Agricultural Head coac...