Пошук в глибину
Пошук в глибину (обхід в глибину, DFS) - це один з основних алгоритмів на графах.
В результаті пошуку в глибину знаходиться лексикографічно перший шлях в графі.
Алгоритм працює за , де - кількість вершин, - кількість ребер.
Алгоритм
TODO: add detailed description for DFS.
Реалізація
Найпростіша реалізація:
vector<vector<int>> g; // граф, список суміжності
int n; // кількість вершин
vector<bool> visited(n); // відвідані вершини
void dfs(int v) {
visited[v] = true;
for (int i = 0; i < g[v].size(); i++) {
int to = g[v][i];
if (!visited[to]) {
dfs(to);
}
}
}
Інколи необхідно знати кольори вершин (0 - не відвідана вершина; 1 - відвідана вершина, але досі у стеці; 2 - відвідана і більше немає у стеці) та "час" заходу та виходу з вершин. Ці допоміжні величини використовуються у декількох наведених прикладах застосування алгоритму.
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 (int i = 0; i < g[v].size(); i++) {
int to = g[v][i];
if (color[to] == 0) {
dfs(to);
}
}
color[v] = 2;
time_out[v] = dfs_timer++;
}
Застосування
Пошук будь-якого шляху у графі.
Пошук лексикографічно першого шляху в графі.
Перевірка чи одна вершина дерева є предком іншої.
На початку і у кінці ітерації пошуку в глибину будемо запам'ятовувати "час" заходу і виходу з кожної вершині. Тепер за можна знайти відповідь: вершина є предком вершини тоді і тільки тоді, коли та .
Запускаємо серію пошуків в глибину, щоб обійти всі вершини графа. Відсортуємо вершини по спаданню часу виходу - це і буде відповіддю.
Пошук компонент сильної зв'язності.
Спочатку проводимо топологічне сортування, а потім транспонуємо граф. Після того знову проводимо серію пошуків у глибину, але в порядку вершин, який було отримано топологічним сортуванням. Кожне дерево пошуку - сильнозв'язана компонента.
Спочатку перетворюємо граф в орієнтований, роблячи серію пошуків в глибину, і орієнтуючи кожне ребро так, як ми намагалися по ньому пройти. Потім знаходимо сильнозв'язані компоненти. Мостами є ті ребра, кінці яких належать різним сильнозв'язаним компонентам.
Задачі
e-olymp - 122 - Маршрути в горах | Розв'язки: C++
e-olymp - 977 - Дерево? | Розв'язки: C++
e-olymp - 978 - Отримай дерево | Розв'язки: C#
e-olymp - 1941 - Предок | Розв'язки: C++
e-olymp - 2270 - Пошук циклу | Розв'язки: C++
e-olymp - 2382 - Графічна маска | Розв'язки: C++
e-olymp - 2383 - Електричні провода | Розв'язки: C++
e-olymp - 3165 - Двокольоровість | Розв'язки: C++
e-olymp - 4077 - Зарплата в корпорації | Розв'язки: C++