Поиск в глубину (DFS): различия между версиями

[досмотренная версия]

Текущая версия от 07:19, 7 июля 2022

Свойства и структура алгоритма

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

Поиск в глубину^[1] (англ. Depth-First Search) является составной частью многих графовых алгоритмов (поиск компонент сильной связности и двусвязности, мостов, решение задачи о назначениях, проверка планарности графа, определение вершинной и рёберной связности). Результатом поиска в глубину может являться, например, дерево обхода и нумерация вершин (в прямом или обратном порядке). Сложность алгоритма [math]\displaystyle{ O(m) }[/math].

Математическое описание алгоритма

Вычислительное ядро алгоритма

Макроструктура алгоритма

Схема реализации последовательного алгоритма

Последовательная сложность алгоритма

Алгоритм выполняет ограниченный объём работы для каждого ребра, поэтому его сложность составляет [math]\displaystyle{ O(m) }[/math].

Информационный граф

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

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

Реализация поиска в ширину на распределённых графах описана в работах^[2]^[3].

Входные и выходные данные алгоритма

Свойства алгоритма

Программная реализация алгоритма

Особенности реализации последовательного алгоритма

Возможные способы и особенности параллельной реализации алгоритма

Результаты прогонов

Выводы для классов архитектур

Литература

↑ Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.
↑ 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.
↑ 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.

[1] Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.

[2] 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.

[3] 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.

[1]

[2]

[3]

@@ Строка 1: / Строка 1: @@
+{{level-a}}
 == Свойства и структура алгоритма ==
 === Общее описание алгоритма ===
@@ Строка 24: / Строка 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>).
 == Литература ==
@@ Строка 45: / Строка 35: @@
 [[Категория:Начатые статьи]]
+[[en:Depth-first search (DFS)]]