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

[непроверенная версия]

Версия от 14:36, 11 июня 2015

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Описание локальности данных и вычислений

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

Масштабируемость алгоритма и его реализации

Динамические характеристики и эффективность реализации алгоритма

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

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

Boost Graph Library (функции depth_first_search, depth_first_visit, undirected_dfs).

Литература

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

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

[1]

@@ Строка 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>.
 === Математическое описание ===