Изменения
Нет описания правки
=Постановка задачи = Использование обхода Пусть дан ориентированный граф без петель и кратных рёбер. Требуется проверить наличие цикла в этом графе. Решим эту задачу с помощью поиска в глубину за O (M). = Алгоритм = Произведём серию поисков в глубину для поиска цикла в ориентированном графе . Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе - в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли цикл. Сам цикл можно восстановить проходом по массиву предков. = Реализация = Здесь приведена реализация алгоритма на С++. ===С++=== vector < vector<int> > graph; vector<int> color; void dfs(int node_index) { color[node_index] = 1; for (vector<int>::iterator i = graph[node_index].begin(); i != graph[node_index].end(); ++i) { if ( color[*i] == 0 ) dfs(*i); if ( color[*i] ==1 ) out } color[node_index] =2; }
