Алгоритм Прима - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:12:40Z

rollbackEdits.php mass rollback

94.16.121.91 в 05:56, 1 сентября 2022

2022-09-01T05:56:21Z

178.252.127.226: /* Пример */

2018-06-15T18:14:22Z

‎Пример

178.252.127.226: /* Пример */

2018-06-15T18:13:10Z

‎Пример

Shersh: /* Источники информации */ категория

2015-09-07T17:59:25Z

‎Источники информации: категория

5.45.192.105: /* Пример */

2014-11-01T16:48:44Z

‎Пример

188.227.78.184 в 15:59, 1 ноября 2014

2014-11-01T15:59:52Z

Shersh: /* Реализация */ от'mathtt'счено

2014-10-14T19:51:08Z

‎Реализация: от'mathtt'счено

Shersh: /* Реализация */

2014-10-14T19:47:30Z

‎Реализация

Shersh: /* Реализация */ псевдокод в \mathtt

2014-10-14T09:40:43Z

‎Реализация: псевдокод в \mathtt

← Предыдущая		Версия 16:12, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Алгоритм Прима''' (англ. ''Prim's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Минимальное остовное дерево\|минимального остовного дерева]] (англ. ''minimum spanning tree, MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы \| неориентированном связном графе]].		'''Алгоритм Прима''' (англ. ''Prim's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Минимальное остовное дерево\|минимального остовного дерева]] (англ. ''minimum spanning tree, MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы \| неориентированном связном графе]].

← Предыдущая		Версия 05:56, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Алгоритм Прима''' (англ. ''Prim's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Минимальное остовное дерево\|минимального остовного дерева]] (англ. ''minimum spanning tree, MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы \| неориентированном связном графе]].		'''Алгоритм Прима''' (англ. ''Prim's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Минимальное остовное дерево\|минимального остовного дерева]] (англ. ''minimum spanning tree, MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы \| неориентированном связном графе]].

@@ Строка 47: / Строка 47: @@
 | <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex>\infty</tex> || <tex> 1 </tex>
 |}
-|style="padding-left: 1em" |Теперь минимальный приоритет у вершины '''е'''.<br/> Извлечём её и рассмотрим смежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим п.риоритет только у вершины '''d''', так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавлено в ответ.
+|style="padding-left: 1em" |Теперь минимальный приоритет у вершины '''е'''.<br/> Извлечём её и рассмотрим смежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим приоритет только у вершины '''d''', так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавлено в ответ.
 |-
 |[[Файл:Mst_prima_3.png|200px]]

@@ Строка 47: / Строка 47: @@
 | <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex>\infty</tex> || <tex> 1 </tex>
 |}
-|style="padding-left: 1em" |Теперь минимальный приоритет у вершины '''е'''.<br/> Извлечём её и рассмотрим смежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим приоритет только у вершины '''d''', так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавлено в ответ.
+|style="padding-left: 1em" |Теперь минимальный приоритет у вершины '''е'''.<br/> Извлечём её и рассмотрим смежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим п.риоритет только у вершины '''d''', так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавлено в ответ.
 |-
 |[[Файл:Mst_prima_3.png|200px]]

← Предыдущая		Версия 17:59, 7 сентября 2015
Строка 100:		Строка 100:
	[[Категория: Алгоритмы и структуры данных]]		[[Категория: Алгоритмы и структуры данных]]
	[[Категория: Остовные деревья ]]		[[Категория: Остовные деревья ]]
		+	[[Категория: Построение остовных деревьев]]

@@ Строка 38: / Строка 38: @@
 | <tex> 0 </tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
 |}
-|style="padding-left: 1em" | Извлечём из множества вершину '''a''', так как её приоритет минимален.<br/>Рассмотрим смежные с ней вершины '''b''', '''c''', и '''e'''. <br/>Обновим их приоритеты, как веса соответствующих рёбер '''ab''', '''ac''' и '''ae''', которые будут добавленны в ответ.
+|style="padding-left: 1em" | Извлечём из множества вершину '''a''', так как её приоритет минимален.<br/>Рассмотрим смежные с ней вершины '''b''', '''c''', и '''e'''. <br/>Обновим их приоритеты, как веса соответствующих рёбер '''ab''', '''ac''' и '''ae''', которые будут добавлены в ответ.
 |-
 |[[Файл:Mst_prima_2.png|200px]]
@@ Строка 47: / Строка 47: @@
 | <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex>\infty</tex> || <tex> 1 </tex>
 |}
-|style="padding-left: 1em" |Теперь минимальный приоритет у вершины '''е'''.<br/> Извлечём её и рассмотрим смежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим приоритет только у вершины '''d''', так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавленно в ответ.
+|style="padding-left: 1em" |Теперь минимальный приоритет у вершины '''е'''.<br/> Извлечём её и рассмотрим смежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим приоритет только у вершины '''d''', так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавлено в ответ.
 |-
 |[[Файл:Mst_prima_3.png|200px]]

← Предыдущая		Версия 15:59, 1 ноября 2014
Строка 1:		Строка 1:
−	'''Алгоритм Прима''' (англ. ''Prim's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Минимальное остовное дерево\|минимального остовного дерева]] (англ. ''minimum spanning tree, MST'') во взвешенном [[~~Основные_определения_теории_графов~~#~~.D0.9D.D0.B5.D0.BE.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B~~ \| неориентированном связном графе]].	+	'''Алгоритм Прима''' (англ. ''Prim's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Минимальное остовное дерево\|минимального остовного дерева]] (англ. ''minimum spanning tree, MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы \| неориентированном связном графе]].

	== Идея ==		== Идея ==

@@ Строка 13: / Строка 13: @@
      <tex>r\ =</tex> произвольная вершина графа <tex>G</tex>
      <tex>\mathtt{key}[r]\ =\ \mathtt{0}</tex>
-     <tex>Q.\mathrm{push}(V(G))</tex>
+     <tex>Q.\mathtt{push}(V(G))</tex>
-     '''while not''' <tex>\mathtt{Q.isEmpty()}</tex>
+     '''while not''' <tex>Q.\mathtt{isEmpty()}</tex>
          <tex>v\ =\ Q.\mathtt{extractMin}()</tex>
          '''for''' <tex>vu \in E(G)</tex>
@@ Строка 20: / Строка 20: @@
                  <tex>\mathtt{p}[u]\ =\ v</tex>
                  <tex>\mathtt{key}[u]\ =\ w(v, u)</tex>
-                 <tex>Q.\mathrm{decreaseKey}(u, \mathtt{key}[u])</tex>
+                 <tex>Q.\mathtt{decreaseKey}(u, \mathtt{key}[u])</tex>
 Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.<br>

@@ Строка 7: / Строка 7: @@
   <font color=green>// <tex>G</tex> {{---}} исходный граф</font>
   <font color=green>// <tex>w</tex> {{---}} весовая функция</font>
-  '''function''' primFindMST():
+  '''function''' <tex>\mathtt{primFindMST}():</tex>
-     '''for''' v '''in''' V
+     '''for''' <tex>v \in V(G)</tex>
-         key[v] = <tex>\infty</tex>
+         <tex>\mathtt{key}[v]\ =\ \infty</tex>
-         p[v] = ''null''
+         <tex>\mathtt{p}[v]\ =</tex> ''null''
-     r = произвольная вершина графа G
+     <tex>r\ =</tex> произвольная вершина графа <tex>G</tex>
-     key[r] = 0
+     <tex>\mathtt{key}[r]\ =\ \mathtt{0}</tex>
-     Q.push(V)
+     <tex>Q.\mathrm{push}(V(G))</tex>
-     '''while not''' Q.isEmpty()
+     '''while not''' <tex>Q.\mathtt{isEmpty}()</tex>
-         v = Q.extractMin()
+         <tex>v\ =\ Q.\mathtt{extractMin}()</tex>
-         '''for''' vu '''in''' E
+         '''for''' <tex>vu \in E(G)</tex>
-             '''if''' u '''in''' Q '''and''' key[u] > w(v, u)
+             '''if''' <tex>u \in Q</tex> '''and''' <tex>\mathtt{key}[u] > w(v, u)</tex>
-                 p[u] = v
+                 <tex>\mathtt{p}[u]\ =\ v</tex>
-                 key[u] = w(v, u)
+                 <tex>\mathtt{key}[u]\ =\ w(v, u)</tex>
-                 Q.decreaseKey(u, key[u])
+                 <tex>Q.\mathrm{decreaseKey}(u, \mathtt{key}[u])</tex>
 Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.<br>