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

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

Версия 17:36, 11 июня 2015

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритмов
3 Литература

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 Литература

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