Обход в глубину, цвета вершин - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:38:11Z

rollbackEdits.php mass rollback

23.128.248.38 в 03:45, 1 сентября 2022

2022-09-01T03:45:15Z

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

2018-06-19T18:45:38Z

‎Реализация

Lapenok.aleksej: Откат правок 93.85.153.53 (обсуждение) к версии Shersh

2018-03-12T17:41:42Z

Откат правок 93.85.153.53 (обсуждение) к версии Shersh

Внесённые изменения

93.85.153.53: Полностью удалено содержимое страницы

2018-03-09T19:27:05Z

Полностью удалено содержимое страницы

Внесённые изменения

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

2016-12-18T10:33:38Z

‎Реализация

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

2016-12-18T10:33:17Z

‎Реализация

Artem Ivanov в 11:37, 17 декабря 2016

2016-12-17T11:37:11Z

Artem Ivanov в 06:44, 16 декабря 2016

2016-12-16T06:44:19Z

Artem Ivanov в 06:39, 16 декабря 2016

2016-12-16T06:39:26Z

Внесённые изменения

← Предыдущая		Версия 16:38, 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 Майкл Наки].
−	\|}
−
	'''Обход в глубину''' (поиск в глубину, англ. ''Depth-First Search'', ''DFS'') — один из основных методов обхода [[Основные определения теории графов\|графа]], часто используемый для [[Использование обхода в глубину для проверки связности\|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе\|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности\|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки\|топологической сортировки]].		'''Обход в глубину''' (поиск в глубину, англ. ''Depth-First Search'', ''DFS'') — один из основных методов обхода [[Основные определения теории графов\|графа]], часто используемый для [[Использование обхода в глубину для проверки связности\|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе\|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности\|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки\|топологической сортировки]].

← Предыдущая		Версия 03:45, 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 Майкл Наки].
		+	\|}
		+
	'''Обход в глубину''' (поиск в глубину, англ. ''Depth-First Search'', ''DFS'') — один из основных методов обхода [[Основные определения теории графов\|графа]], часто используемый для [[Использование обхода в глубину для проверки связности\|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе\|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности\|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки\|топологической сортировки]].		'''Обход в глубину''' (поиск в глубину, англ. ''Depth-First Search'', ''DFS'') — один из основных методов обхода [[Основные определения теории графов\|графа]], часто используемый для [[Использование обхода в глубину для проверки связности\|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе\|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности\|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки\|топологической сортировки]].

@@ Строка 47: / Строка 47: @@
   '''function''' doDfs(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font>
-     visited = array[n, ''white'']
+    color = array[n, ''white'']
      '''function''' dfs(u: '''int'''):

@@ Строка 47: / Строка 47: @@
   '''function''' doDfs(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font>
-    fill(color, ''white'')
+     visited = array[n, ''white'']
      '''function''' dfs(u: '''int'''):
@@ Строка 59: / Строка 59: @@
         '''if''' color[i] == ''white''
            dfs(i)
-−
 === Пример ===
 Рассмотрим, как будут изменяться цвета вершин при обходе в глубину данного графа.

@@ Строка 17: / Строка 17: @@
   '''function''' doDfs(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font>
-     fill(visited, ''false'')
+     visited = array[n, ''false''] <font color=darkgreen> // создаём массив посещённых вершины длины n, заполненный ''false'' изначально</font>
      '''function''' dfs(u: '''int'''):
@@ Строка 27: / Строка 27: @@
      '''for''' i = 1 '''to''' n
         '''if''' '''not''' visited[i]
            dfs(i)
 === Время работы ===

@@ Строка 16: / Строка 16: @@
 В массиве <tex>\mathrm{visited[]}</tex> хранится информация о ''пройденных'' и ''не пройденных'' вершинах.
-  '''function''' doDfs(G: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font>
+  '''function''' doDfs(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font>
      '''function''' dfs(u: '''int'''):
         visited[u] = ''true''
@@ Строка 23: / Строка 25: @@
               dfs(v)
      '''for''' i = 1 '''to''' n
         '''if''' '''not''' visited[i]
@@ Строка 29: / Строка 30: @@
 === Время работы ===
-Оценим время работы обхода в глубину. Процедура <tex>\mathrm{dfs}</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ begin(e) = u\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>.
+Оценим время работы обхода в глубину. Процедура <tex>\mathrm{dfs}</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ \mathrm{begin(e)} = u\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>.
 == Цвета вершин ==
@@ Строка 45: / Строка 46: @@
 Отличие реализации с цветами от предыдущей лишь в массиве <tex>\mathrm{visited[]}</tex>, который мы назовем теперь <tex>\mathrm{color[]}</tex>. В нем будет хранится информация о цветах вершин.
-  '''function''' doDfs(G: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font>
+  '''function''' doDfs(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font>
      '''function''' dfs(u: '''int'''):
         color[u] = ''gray''
@@ Строка 53: / Строка 56: @@
         color[u] = ''black''
      '''for''' i = 1 '''to''' n
         '''if''' color[i] == ''white''