MAXimal
home
algo
bookz
forum
about
Поиск в глубину и его приложения
Page source on the
HTML
language:
<h1>Поиск в глубину</h1> <p>Это один из основных алгоритмов на графах.</p> <p>В результате поиска в глубину находится лексикографически первый путь в графе.</p> <p>Алгоритм работает за <b>O (N+M)</b>.</p> <h2>Применения алгоритма</h2> <ul> <li>Поиск любого пути в графе.</li> <li>Поиск лексикографически первого пути в графе.</li> <li>Проверка, является ли одна вершина дерева предком другой:<br>В начале и конце итерации поиска в глубину будет запоминать "время" захода и выхода в каждой вершине. Теперь за O(1) можно найти ответ: вершина i является предком вершины j тогда и только тогда, когда start<sub>i</sub> < start<sub>j</sub> и end<sub>i</sub> > end<sub>j</sub>.</li> <li><algohref=lca>Задача LCA (наименьший общий предок)</algohref>.</li> <li><algohref=topological_sort>Топологическая сортировка</algohref>:<br>Запускаем серию поисков в глубину, чтобы обойти все вершины графа. Отсортируем вершины по времени выхода по убыванию - это и будет ответом.</li> <li><algohref=finding_cycle>Проверка графа на ацикличность и нахождение цикла</algohref></li> <li><algohref=strong_connected_components>Поиск компонент сильной связности</algohref>:<br>Сначала делаем топологическую сортировку, потом транспонируем граф и проводим снова серию поисков в глубину в порядке, определяемом топологической сортировкой. Каждое дерево поиска - сильносвязная компонента.</li> <li><algohref=bridge_searching>Поиск мостов</algohref>:<br>Сначала превращаем граф в ориентированный, делая серию поисков в глубину, и ориентируя каждое ребро так, как мы пытались по нему пройти. Затем находим сильносвязные компоненты. Мостами являются те рёбра, концы которых принадлежат разным сильносвязным компонентам.</li> </ul> <h2>Реализация</h2> <code>vector < vector<int> > g; // граф int n; // число вершин vector<int> color; // цвет вершины (0, 1, или 2) vector<int> time_in, time_out; // "времена" захода и выхода из вершины int dfs_timer = 0; // "таймер" для определения времён void dfs (int v) { time_in[v] = dfs_timer++; color[v] = 1; for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i) if (color[*i] == 0) dfs (*i); color[v] = 2; time_out[v] = dfs_timer++; }</code> <p>Это наиболее общий код. Во многих случаях времена захода и выхода из вершины не важны, так же как и не важны цвета вершин (но тогда надо будет ввести аналогичный по смыслу булевский массив used). Вот наиболее простая реализация:</p> <code>vector < vector<int> > g; // граф int n; // число вершин vector<char> used; void dfs (int v) { used[v] = true; for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i) if (!used[*i]) dfs (*i); }</code>