Проверка графа на наличие циклов
Нам необходимо ответить на вопрос: “А содержит ли данный граф хоть один цикл?”. Напомним, что циклом в теории графов называют путь, в котором начало и конец совпадают.
Стоит отметить, что нам в данном случае просто необходимо установить факт наличия цикла в графе. Найти эти самые циклы — задача более сложного порядка.
Алгоритм
Для поиска будем использовать DFS. Рассмотрим дерево рекурсивных вызовов в нашем графе:
Как мы видим, существует восходящее (красное) ребро, по которому DFS не спускался. Данное ребро ведет в такого соседа, который не является прямым предком данной вершины. Это является признаком цикла в графе, и таким образом, мы можем организовать проверку на наличие цикла (циклов).
bool used[100]; vector vectorint>> graph(100); void dfs(int vertex, int parent = -1)// parent - предок текущей вершины used[vertex] = true; for (auto neighbor : graph[vertex]) if (!used[neighbor]) dfs(neighbor,vertex); else if(neighbor != parent) cout <"Grath has a cycle!"; exit(0); // выйти из программы > > > int main() int n; cout <"Enter the number of edges: "; cin >> n; for (int i = 0; i n; i++) int a, b; cin >> a >> b; graph[a].push_back(b); > dfs(1); // начинаем обход с первой вершины cout <"graph has no cycles";// если мы принудительно не вышли из программы, значит в графе нет циклов return 0; >Проверка графа на цикл
@RomanAlexandrovich прямо из e-maxx цитирую: Произведём серию поисков в глубину в графе. Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе — в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли цикл (если граф неориентированный, то случаи, когда поиск в глубину из какой-то вершины пытается пойти в предка, не считаются).
Проверка графа на наличие циклов
Для заданного графа нужно ответить, содержит ли он хотя бы один цикл. Стоит заметить, что от нас не требуется найти все циклы, нужно всего лишь ответить, существует ли хотя бы один. Задача на поиск всех циклов решается гораздо сложнее.
Алгоритм
Для поиска цикла будем использовать DFS. Для примера разберём такой граф:
Допустим, мы запустили DFS из вершины 1, и он полностью обошёл граф. Представим обход этого графа так же, как представляем деревья, по уровням в зависимости от глубины рекурсии:
(Примечание: это только один из возможных вариантов обхода в глубину.)
Как видите по одному из ребёр, входящих в цикл, DFS не спускался: оно выделено красным цветом. Именно по наличию таких “восходящих” рёбер в графе можно судить о наличии в нём циклов. При реализации DFS такие рёбра распознать достаточно легко: они ведут в уже посещённую (\(used\)) вершину, но не в прямого предка (\(p\)).
Реализация
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34#include using namespace std; vectorint> graph[100000]; bool used[100000]; void dfs(int v, int p = -1) //p - прямой предок used[v] = true; for (int u: graph[v]) if (!used[u]) dfs(u, v); > else if (u != p) cout <"Graph has cycles."; exit(0); //Полностью выйти из программы. > > > int main() //Ввод графа. //Проверяем отдельно каждую вершину, так как //граф может быть несвязным, но всё равно иметь циклы for (int i = 0; i n; i++) if (!used[i]) dfs(i); > > //Если мы ещё не вышли не вышли из программы, в графе нет циклов. cout <"Graph has no cycles."; >Проверка графа на цикл
Проверка на связность графа
Здравствуйте, помогите пожалуйста. Есть неориентированный граф. Представлен граф список смежности.Проверка графа на связность
Требуется проверить граф на связность. Помогите найти ошибки. #include <stdio.h> #include.Алгоритм Дейкстры и цикл for (для заполнения веса рёбер графа)
Здравствуйте, форумчане. Задался я написанием алгоритма Дейкстры, но возникла проблема в одном.проверка графа на связность
помогитте написать программу проверяющую граф на связность. граф задаётся в текстовом файле в виде.
