Для неориентированного графа G = (V, E) с n вершинами (| V | = n), как вы находите, если он содержит цикл в O (n)?
Циклы в несанкционированном графике
Ответ 1
Я думаю, что глубина первого поиска решает его. Если неисследованный край приводит к ранее посещенному node, тогда график содержит цикл. Это условие также делает его O (n), так как вы можете исследовать максимум n ребер, не устанавливая его в true или оставаясь без неизведанных ребер.
Ответ 2
На самом деле поиск глубины сначала (или даже в ширину) не достаточно. Вам нужен более зрелищный более сложный алгоритм.
Например, предположим, что существует граф с узлами {a, b, c, d} и ребрами {(a, b), (b, c), (b, d), (d, c)}, где an edge (x, y) - ребро от x до y. (выглядит примерно так, со всеми краями, направленными вниз).
(a)
|
|
(b)
/ \
(d) |
| |
\ /
(c)
Затем, делая глубину первого поиска, можно посетить node a, затем b, затем c, затем вернуться к c, затем посетить d и, наконец, снова посетить c и завершить цикл, когда этого не произойдет. Аналогичная вещь происходит с первой.
Что вам нужно сделать, так это следить за тем, какие узлы вы посередине посещаете. В приведенном выше примере, когда алгоритм достигает (d), он завершил посещение (c), но не (a) или (b). Поэтому пересмотр готового node в порядке, но посещение незавершенного node означает, что у вас есть цикл. Обычный способ сделать это - цвет каждого node белый (еще не посещенный), серый (посещение потомков) или черный (завершено посещение).
вот какой-то псевдокод!
define visit(node n):
if n.colour == grey: //if we're still visiting this node or its descendants
throw exception("Cycle found")
n.colour = grey //to indicate this node is being visited
for node child in n.children():
if child.colour == white: //if the child is unexplored
visit(child)
n.colour = black //to show we're done visiting this node
return
то запуск посещения (root_node) вызовет исключение, если и только если есть цикл (изначально все узлы должны быть белыми).
Извините, если вы все это уже знаете, вполне возможно, что вы имели ввиду глубину первого поиска в любом случае, но я надеюсь, что это поможет.
Ответ 3
Связный, неориентированный граф G, не имеющий циклов, является деревом! Любое дерево имеет ровно n - 1 ребра, поэтому мы можем просто пересечь список ребер графа и подсчитать края. Если мы подсчитаем n - 1 ребра, мы вернем "да", но если мы достигнем n-го края, мы вернем "нет". Это занимает время O (n), потому что мы смотрим не более n ребер.
Но если граф не подключен, нам нужно будет использовать DFS. Мы можем проходить по краям, и если любые неисследованные ребра приводят к посещенной вершине, тогда он имеет цикл.
Ответ 4
Вы можете решить эту проблему с помощью DFS. Сложность времени: O (n)
Суть алгоритма заключается в том, что если подключенный компонент/граф НЕ содержит ЦИКЛ, он всегда будет TREE. См. здесь для доказательства
Предположим, что график не имеет цикла, т.е. является деревом. И если мы посмотрим на дерево, каждое ребро из node:
1. либо достигает своего единственного родителя, который на один уровень выше него.
2.or достигает своих детей, которые находятся на одном уровне ниже.
Итак, если a node имеет любое другое ребро, которое не относится к двум описанным выше, оно, очевидно, свяжет node с одним из своих предков, отличных от его родителя. Это сформирует ЦИКЛ.
Теперь, когда факты понятны, все, что вам нужно сделать, - это запустить DFS для графика (учитывая, что ваш граф подключен, в противном случае это делается для всех невидимых вершин) и ЕСЛИ вы найдете соседа из node, который ПОСЕТИЛ, а не его родитель, тогда мой друг на графике есть ЦИКЛ, и вы ДОЛЖНЫ.
Вы можете отслеживать родителя, просто передавая родительский параметр как параметр, когда вы делаете DFS для своих соседей. И поскольку вам нужно всего лишь изучить n ребер, сложность времени будет O (n).
Надеюсь, что ответ помог.
Ответ 5
Кстати, если вы знаете, что это связано, то просто это дерево (таким образом, нет циклов) тогда и только тогда, когда |E|=|V|-1. Конечно, это не маленький объем информации:)
Ответ 6
Ответ: на самом деле, первый поиск по ширине (или поиск по глубине сначала не имеет значения). Детали лежат в анализе.
Теперь, насколько быстро алгоритм?
Сначала представьте, что график не имеет циклов. Число ребер тогда равно O (V), график - это лес, цель достигнута.
Теперь представьте, что график имеет циклы, и ваш алгоритм поиска завершит и сообщит об успехе в первом из них. Граф неориентирован, и, следовательно, когда алгоритм проверяет ребро, есть только две возможности: либо он посетил другой конец ребра, либо он имеет, а затем, это ребро закрывает круг. И как только он видит другую вершину ребра, эта вершина "проверяется", поэтому есть только O (V) этих операций. Второй случай будет достигнут только один раз на протяжении всего алгоритма.
Ответ 7
Я считаю, что предположение о том, что граф связан, может быть немногочисленным. таким образом, вы можете использовать доказательство, показанное выше, что время работы O (| V |). если нет, то | E | > | V |. напоминание: время работы DFS O (| V | + | E |).
Ответ 8
Вот код, который я написал в C на основе DFS, чтобы узнать, связан ли данный граф/циклический или нет. с некоторым количеством выходных данных в конце. Надеюсь, это будет полезно:)
#include<stdio.h>
#include<stdlib.h>
/****Global Variables****/
int A[20][20],visited[20],v=0,count=0,n;
int seq[20],s=0,connected=1,acyclic=1;
/****DFS Function Declaration****/
void DFS();
/****DFSearch Function Declaration****/
void DFSearch(int cur);
/****Main Function****/
int main()
{
int i,j;
printf("\nEnter no of Vertices: ");
scanf("%d",&n);
printf("\nEnter the Adjacency Matrix(1/0):\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&A[i][j]);
printf("\nThe Depth First Search Traversal:\n");
DFS();
for(i=1;i<=n;i++)
printf("%c,%d\t",'a'+seq[i]-1,i);
if(connected && acyclic) printf("\n\nIt is a Connected, Acyclic Graph!");
if(!connected && acyclic) printf("\n\nIt is a Not-Connected, Acyclic Graph!");
if(connected && !acyclic) printf("\n\nGraph is a Connected, Cyclic Graph!");
if(!connected && !acyclic) printf("\n\nIt is a Not-Connected, Cyclic Graph!");
printf("\n\n");
return 0;
}
/****DFS Function Definition****/
void DFS()
{
int i;
for(i=1;i<=n;i++)
if(!visited[i])
{
if(i>1) connected=0;
DFSearch(i);
}
}
/****DFSearch Function Definition****/
void DFSearch(int cur)
{
int i,j;
visited[cur]=++count;
seq[count]=cur;
for(i=1;i<count-1;i++)
if(A[cur][seq[i]])
acyclic=0;
for(i=1;i<=n;i++)
if(A[cur][i] && !visited[i])
DFSearch(i);
}
/* Результат вывода:
[email protected]:~/Desktop$ gcc BFS.c
[email protected]:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 10
Enter the Adjacency Matrix(1/0):
0 0 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 0
The Depdth First Search Traversal:
a,1 c,2 d,3 f,4 b,5 e,6 g,7 h,8 i,9 j,10
It is a Not-Connected, Cyclic Graph!
[email protected]:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 4
Enter the Adjacency Matrix(1/0):
0 0 1 1
0 0 1 0
1 1 0 0
0 0 0 1
The Depth First Search Traversal:
a,1 c,2 b,3 d,4
It is a Connected, Acyclic Graph!
[email protected]:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 5
Enter the Adjacency Matrix(1/0):
0 0 0 1 0
0 0 0 1 0
0 0 0 0 1
1 1 0 0 0
0 0 1 0 0
The Depth First Search Traversal:
a,1 d,2 b,3 c,4 e,5
It is a Not-Connected, Acyclic Graph!
*/
Ответ 9
Простая DFS выполняет работу по проверке того, имеет ли данный неориентированный граф цикл или нет.
Идея , используемая в приведенном выше коде:
Если node, который уже обнаружен/посещен, снова найден и а не родительский node, тогда у нас есть цикл.
Это также можно объяснить, как показано ниже (упоминается @Rafał Dowgird
Если неизведанный ребро приводит к ранее посещенному node, тогда график содержит цикл.
Ответ 10
Неориентированный граф ацикличен (т.е. лес), если в DFS нет обратных краев.
Так как задние края - это те ребра (u, v), соединяющие вершину u с предком
v в дереве глубины, поэтому никаких задних кромок означает, что есть только ребра дерева, поэтому
нет цикла.
Поэтому мы можем просто смешать DFS. Если найти задний край, есть цикл. Сложность
O(V ) вместо O(E + V ). Поскольку, если есть задний край, он должен
прежде чем увидеть |V | различные края. Это происходит потому, что в ациклическом (неориентированном) лесу |E| ≤ |V | + 1.
Ответ 11
Как говорили другие... Глубокий первый поиск поможет решить эту проблему. В общей глубине первый поиск принимает O (V + E), но в этом случае вы знаете, что граф имеет не более O (V) ребер. Таким образом, вы можете просто запустить DFS, и как только вы увидите, что новый фронт увеличивает счетчик. Когда счетчик достиг V, вам не нужно продолжать, потому что график имеет определенный цикл. Очевидно, что это принимает O (v).
Ответ 12
Я считаю, что использование DFS правильно также зависит от того, как вы собираетесь представлять свой граф в коде. Например, предположим, что вы используете смежные списки для отслеживания соседних узлов, и ваш граф имеет 2 вершины и только одно ребро: V = {1,2} и E = {(1,2)}. В этом случае, начиная с вершины 1, DFS будет отмечать ее как ПОСЕТИТЕЛЯ и будет помещать 2 в очередь. После этого он будет поп-вершиной 2, а так как 1 смежна с 2, а 1 - ПОСЕТИЛ, DFS сделает вывод о том, что существует цикл (что неверно). Другими словами, в Undirected графах (1,2) и (2,1) есть одно и то же ребро, и вы должны кодировать таким образом, чтобы DFS не учитывала их разные ребра. Сохранение родительского node для каждого посещенного node поможет справиться с этой ситуацией.
Ответ 13
Недавно я начал изучать графики. Я написал фрагмент кода в java, который мог бы определить, имеет ли граф циклы. Я использовал DFT для поиска циклов на графике. Вместо recurssion я использовал стек для перемещения графика.
На высоком уровне DFT с использованием стека выполняется в следующих шагах
- Посетите Node
- Если node не находится в списке посещений, добавьте его в список и нажмите его в верхнюю часть стека
- Отметьте node в верхней части стека как текущий node.
- Повторите описанное выше для каждого смежного node текущего Node
- Если все узлы были посещены, вытащите текущий node из стека
Я выполнил ДПФ из каждого node Графа и во время обхода, если я столкнулся с вершиной, которую я посетил ранее, я проверил, имела ли вершина глубина стека больше единицы. Я также проверил, имел ли node ребро для себя и если между узлами было несколько ребер. Версия стека, которую я изначально написал, была не очень элегантной. Я прочитал псевдокод о том, как это можно сделать, используя рекурсию, и это было аккуратно. Вот реализация Java. Массив LinkedList представляет собой график. с каждым node и смежными вершинами, обозначенными индексом массива, и каждый элемент соответственно
class GFG {
Boolean isCyclic(int V, LinkedList<Integer>[] alist) {
List<Integer> visited = new ArrayList<Integer>();
for (int i = 0; i < V; i++) {
if (!visited.contains(i)) {
if (isCyclic(i, alist, visited, -1))
return true;
}
}
return false;
}
Boolean isCyclic(int vertex, LinkedList<Integer>[] alist, List<Integer> visited, int parent) {
visited.add(vertex);
for (Iterator<Integer> iterator = alist[vertex].iterator(); iterator.hasNext();) {
int element = iterator.next();
if (!visited.contains(element)) {
if (isCyclic(element, alist, visited, vertex))
return true;
} else if (element != parent)
return true;
}
return false;
}
}
Ответ 14
Вы можете использовать расширенную графическую библиотеку и циклические зависимости. Он имеет решение для поиска циклов с функцией back_edge.
Ответ 15
Неориентированный граф без цикла имеет | E | < | V |. -1
public boolean hasCycle(Graph g) {
int totalEdges = 0;
for(Vertex v : g.getVertices()) {
totalEdges += v.getNeighbors().size();
}
return totalEdges/2 > g.getVertices().size - 1;
}