Поиск в глубину (DFS) - История изменений

ASA в 07:19, 7 июля 2022

2022-07-07T07:19:25Z

← Предыдущая версия		Версия от 07:19, 7 июля 2022
Строка 26:		Строка 26:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~

	* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/depth_first_search.html depth_first_search]</code>, <code>[http://www.boost.org/libs/graph/doc/depth_first_visit.html depth_first_visit]</code>, <code>[http://www.boost.org/libs/graph/doc/undirected_dfs.html undirected_dfs]</code>).
	* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/tsin_depth_first_visit.html tsin_depth_first_visit]</code>).
	* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.traversal.depth_first_search.dfs_edges.html dfs_edges]</code>).

	== Литература ==		== Литература ==

ASA в 13:39, 14 марта 2018

2018-03-14T13:39:23Z

← Предыдущая версия		Версия от 13:39, 14 марта 2018
Строка 47:		Строка 47:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

			[[en:Depth-first search (DFS)]]

ASA в 14:09, 6 марта 2018

2018-03-06T14:09:46Z

← Предыдущая версия		Версия от 14:09, 6 марта 2018
Строка 1:		Строка 1:
			{{level-a}}

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

ASA в 10:58, 29 июля 2015

2015-07-29T10:58:17Z

← Предыдущая версия		Версия от 10:58, 29 июля 2015
Строка 43:		Строка 43:

	<references />		<references />

			[[Категория:Начатые статьи]]

ASA в 10:57, 29 июля 2015

2015-07-29T10:57:26Z

← Предыдущая версия		Версия от 10:57, 29 июля 2015
Строка 1:		Строка 1:
	== Свойства и структура ~~алгоритмов~~ ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	'''Поиск в глубину'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> (англ. Depth-First Search) является составной частью многих графовых алгоритмов ([[Алгоритм Тарьяна поиска компонент сильной связности\|поиск компонент сильной связности]] и [[Алгоритм Тарьяна поиска компонент двусвязности\|двусвязности]], [[Алгоритм Тарьяна поиска «мостов» в графе\|мостов]], [[Алгоритм Гопкрофта-Карпа\|решение задачи о назначениях]], проверка планарности графа, [[Связность в графах\|определение вершинной и рёберной связности]]). Результатом поиска в глубину может являться, например, дерево обхода и нумерация вершин (в прямом или обратном порядке). Сложность алгоритма <math>O(m)</math>.		'''Поиск в глубину'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> (англ. Depth-First Search) является составной частью многих графовых алгоритмов ([[Алгоритм Тарьяна поиска компонент сильной связности\|поиск компонент сильной связности]] и [[Алгоритм Тарьяна поиска компонент двусвязности\|двусвязности]], [[Алгоритм Тарьяна поиска «мостов» в графе\|мостов]], [[Алгоритм Гопкрофта-Карпа\|решение задачи о назначениях]], проверка планарности графа, [[Связность в графах\|определение вершинной и рёберной связности]]). Результатом поиска в глубину может являться, например, дерево обхода и нумерация вершин (в прямом или обратном порядке). Сложность алгоритма <math>O(m)</math>.

	=== Математическое описание ===		=== Математическое описание алгоритма ===
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	=== ~~Описание схемы~~ реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

Строка 13:		Строка 13:

	=== Информационный граф ===		=== Информационный граф ===
	=== ~~Описание ресурса~~ параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Поиск в ширину плохо поддаётся параллелизации; существует мнение, что алгоритм является последовательным по сути.		Поиск в ширину плохо поддаётся параллелизации; существует мнение, что алгоритм является последовательным по сути.
Строка 19:		Строка 19:
	Реализация поиска в ширину на распределённых графах описана в работах<ref>Cidon, Isreal. “Yet Another Distributed Depth-First-Search Algorithm.” Information Processing Letters 26, no. 6 (January 1988): 301–5. doi:10.1016/0020-0190(88)90187-1.</ref><ref>Tsin, Y H. “Some Remarks on Distributed Depth-First Search.” Information Processing Letters 82, no. 4 (May 2002): 173–78. doi:10.1016/S0020-0190(01)00273-3.</ref>.		Реализация поиска в ширину на распределённых графах описана в работах<ref>Cidon, Isreal. “Yet Another Distributed Depth-First-Search Algorithm.” Information Processing Letters 26, no. 6 (January 1988): 301–5. doi:10.1016/0020-0190(88)90187-1.</ref><ref>Tsin, Y H. “Some Remarks on Distributed Depth-First Search.” Information Processing Letters 82, no. 4 (May 2002): 173–78. doi:10.1016/S0020-0190(01)00273-3.</ref>.

	=== ~~Описание входных~~ и ~~выходных данных~~ ===		=== Входные и выходные данные алгоритма ===
	=== Свойства алгоритма===		=== Свойства алгоритма ===
	== Программная реализация ~~алгоритмов~~ ==
			== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	=== ~~Описание локальности~~ данных и вычислений ===		=== Локальность данных и вычислений ===
	=== Возможные способы и особенности реализации ~~параллельного~~ алгоритма ===		==== Локальность реализации алгоритма ====
			===== Структура обращений в память и качественная оценка локальности =====
			===== Количественная оценка локальности =====
			=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
			==== Масштабируемость алгоритма ====
			==== Масштабируемость реализации алгоритма ====
	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

Daryin: /* Существующие реализации алгоритма */

2015-06-11T19:13:40Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 19:13, 11 июня 2015
Строка 32:		Строка 32:
	* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/depth_first_search.html depth_first_search]</code>, <code>[http://www.boost.org/libs/graph/doc/depth_first_visit.html depth_first_visit]</code>, <code>[http://www.boost.org/libs/graph/doc/undirected_dfs.html undirected_dfs]</code>).		* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/depth_first_search.html depth_first_search]</code>, <code>[http://www.boost.org/libs/graph/doc/depth_first_visit.html depth_first_visit]</code>, <code>[http://www.boost.org/libs/graph/doc/undirected_dfs.html undirected_dfs]</code>).
	* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/tsin_depth_first_visit.html tsin_depth_first_visit]</code>).		* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/tsin_depth_first_visit.html tsin_depth_first_visit]</code>).
			* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.traversal.depth_first_search.dfs_edges.html dfs_edges]</code>).

	== Литература ==		== Литература ==

	<references />		<references />

Daryin: /* Существующие реализации алгоритма */

2015-06-11T16:36:15Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 16:36, 11 июня 2015
Строка 30:		Строка 30:
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

	* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/depth_first_search.html depth_first_search]</code>, <code>[http://www.boost.org/libs/graph/doc/depth_first_visit.html depth_first_visit]</code>, <code>[http://www.boost.org/libs/graph/doc/undirected_dfs.html undirected_dfs]</code>).		* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/depth_first_search.html depth_first_search]</code>, <code>[http://www.boost.org/libs/graph/doc/depth_first_visit.html depth_first_visit]</code>, <code>[http://www.boost.org/libs/graph/doc/undirected_dfs.html undirected_dfs]</code>).
			* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/tsin_depth_first_visit.html tsin_depth_first_visit]</code>).

	== Литература ==		== Литература ==

	<references />		<references />

Daryin: /* Описание ресурса параллелизма алгоритма */

2015-06-11T16:34:09Z

Описание ресурса параллелизма алгоритма

← Предыдущая версия		Версия от 16:34, 11 июня 2015
Строка 16:		Строка 16:

	Поиск в ширину плохо поддаётся параллелизации; существует мнение, что алгоритм является последовательным по сути.		Поиск в ширину плохо поддаётся параллелизации; существует мнение, что алгоритм является последовательным по сути.

			Реализация поиска в ширину на распределённых графах описана в работах<ref>Cidon, Isreal. “Yet Another Distributed Depth-First-Search Algorithm.” Information Processing Letters 26, no. 6 (January 1988): 301–5. doi:10.1016/0020-0190(88)90187-1.</ref><ref>Tsin, Y H. “Some Remarks on Distributed Depth-First Search.” Information Processing Letters 82, no. 4 (May 2002): 173–78. doi:10.1016/S0020-0190(01)00273-3.</ref>.

	=== Описание входных и выходных данных ===		=== Описание входных и выходных данных ===

Daryin: /* Общее описание алгоритма */

2015-06-11T14:36:57Z

Общее описание алгоритма

← Предыдущая версия		Версия от 14:36, 11 июня 2015
Строка 2:		Строка 2:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	~~Алгоритм поиска~~ в глубину<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> (англ. Depth-First Search) является составной частью многих графовых алгоритмов ([[Алгоритм Тарьяна поиска компонент сильной связности\|поиск компонент сильной связности]] и [[Алгоритм Тарьяна поиска компонент двусвязности\|двусвязности]], [[Алгоритм Тарьяна поиска «мостов» в графе\|мостов]], [[Алгоритм Гопкрофта-Карпа\|решение задачи о назначениях]], проверка планарности графа, [[Связность в графах\|определение вершинной и рёберной связности]]). Результатом поиска в глубину может являться, например, дерево обхода и нумерация вершин (в прямом или обратном порядке). Сложность алгоритма <math>O(m)</math>.		'''Поиск в глубину'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> (англ. Depth-First Search) является составной частью многих графовых алгоритмов ([[Алгоритм Тарьяна поиска компонент сильной связности\|поиск компонент сильной связности]] и [[Алгоритм Тарьяна поиска компонент двусвязности\|двусвязности]], [[Алгоритм Тарьяна поиска «мостов» в графе\|мостов]], [[Алгоритм Гопкрофта-Карпа\|решение задачи о назначениях]], проверка планарности графа, [[Связность в графах\|определение вершинной и рёберной связности]]). Результатом поиска в глубину может являться, например, дерево обхода и нумерация вершин (в прямом или обратном порядке). Сложность алгоритма <math>O(m)</math>.

	=== Математическое описание ===		=== Математическое описание ===

Daryin: /* Существующие реализации алгоритма */

2015-06-10T21:32:41Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 21:32, 10 июня 2015
Строка 27:		Строка 27:
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

			* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/depth_first_search.html depth_first_search]</code>, <code>[http://www.boost.org/libs/graph/doc/depth_first_visit.html depth_first_visit]</code>, <code>[http://www.boost.org/libs/graph/doc/undirected_dfs.html undirected_dfs]</code>).

	== Литература ==		== Литература ==

	<references />		<references />