Использование обхода в глубину для поиска цикла — различия между версиями
(→С++) |
|||
| Строка 20: | Строка 20: | ||
===С++=== | ===С++=== | ||
| − | + | int graph[][]; | |
| − | + | int color[]; | |
| − | + | dfs(int index) | |
| − | + | color[index] = grey; // красит вершину в серый цвет | |
| − | + | for (v : uv - ребра) | |
| − | color[index] = | + | if ( color[v] == white ) |
| − | for ( | + | dfs(v); |
| − | + | if ( color[v] == grey ) | |
| − | if ( color[ | + | print(); // вывод ответа |
| − | dfs( | + | color[index] = black; // красит вершину в черный цвет |
| − | if ( color[ | ||
| − | print(); | ||
| − | |||
| − | color[index] = | ||
| − | |||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Обход в глубину]] | [[Категория: Обход в глубину]] | ||
Версия 16:39, 22 декабря 2010
Постановка задачи
Пусть дан ориентированный граф без петель и кратных рёбер. Требуется проверить наличие цикла в этом графе.
Решим эту задачу с помощью поиска в глубину за O (M).
Алгоритм
Произведём серию поисков в глубину в графе. Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе - в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли цикл.
Сам цикл можно восстановить проходом по массиву предков.
Доказательство
Пусть дан граф . Запустим . Рассмотрим выполнение процедуры поиска в глубину от некоторой вершины . Так как все серые вершины лежат в стеке рекурсии, то для них вершина достижима по белым путям. Тогда если из рассматриваемой вершины существует ребро в серую вершину , то это значит, что из вершины существует путь в и из вершины существует путь в . И так как оба эти пути не пересекаются, то существует цикл.
Реализация
Здесь приведена реализация алгоритма на С++.
С++
int graph[][];
int color[];
dfs(int index)
color[index] = grey; // красит вершину в серый цвет
for (v : uv - ребра)
if ( color[v] == white )
dfs(v);
if ( color[v] == grey )
print(); // вывод ответа
color[index] = black; // красит вершину в черный цвет
