Циклы в несанкционированном графике

Для неориентированного графа G = ( V , E ) с n вершинами (| V | = n ), как вы находите, содержит ли он цикл в O ( n )?

    15 Solutions collect form web for “Циклы в несанкционированном графике”

    Я думаю, что поиск по глубине сначала разрешает его. Если неисследованный край приводит к предварительному узлу, то график содержит цикл. Это условие также делает его O (n), так как вы можете исследовать максимум n ребер, не устанавливая его в true или оставаясь без неизведанных ребер.

    На самом деле поиск глубины сначала (или даже ширины) не достаточно. Вам нужен более зрелищный более сложный алгоритм.

    Например, предположим, что существует граф с узлами {a, b, c, d} и ребрами {(a, b), (b, c), (b, d), (d, c)}, где ребро (x , y) – ребро от x до y. (выглядит примерно так, со всеми краями, направленными вниз).

    (a) | | (b) / \ (d) | | | \ / (c) 

    Затем, выполняя глубину, первый поиск может посещать узел (a), затем (b), затем (c), затем возвращаться к (b), затем посещать (d) и, наконец, посещать (c) снова и заключать, что существует цикл – когда нет. Аналогичная вещь происходит с первой.

    Что вам нужно сделать, это следить за тем, какие узлы вы посередине посещаете. В приведенном выше примере, когда алгоритм достигает (d), он завершил посещение (c), но не (a) или (b). Поэтому пересмотр готового узла является хорошим, но посещение незавершенного узла означает, что у вас есть цикл. Обычный способ сделать это – цвет каждого узла белый (еще не посещенный), серый (посещая потомки) или черный (завершено посещение).

    вот какой-то псевдокод!

     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) будет генерировать исключение тогда и только тогда, когда есть цикл (изначально все узлы должны быть белыми).

    Связанный, неориентированный граф G, не имеющий циклов, является деревом! Любое дерево имеет ровно n – 1 ребра, поэтому мы можем просто пересечь список ребер графа и подсчитать края. Если мы подсчитаем n – 1 ребра, мы вернем «да», но если мы достигнем n-го края, мы вернем «нет». Это занимает время O (n), потому что мы смотрим не более n ребер.

    Но если граф не связан, тогда нам придется использовать DFS. Мы можем проходить по краям, и если любые неисследованные ребра приводят к посещенной вершине, то она имеет цикл.

    Вы можете решить эту проблему с помощью DFS. Сложность времени: O (n)

    Суть алгоритма в том, что если подключенный компонент / граф НЕ содержит ЦИКЛ, он всегда будет TREE. См. Здесь для доказательства

    Предположим, что график не имеет цикла, т. Е. Является деревом. И если мы посмотрим на дерево, каждое ребро из узла:

    1. либо достигает своего единственного родителя, что на один уровень выше него.

    2.or достигает своих детей, которые находятся на одном уровне ниже.

    Поэтому, если узел имеет любое другое ребро, которое не относится к двум описанным выше, оно, очевидно, свяжет узел с одним из его предков, отличным от его родителя. Это сформирует ЦИКЛ.

    Теперь, когда факты понятны, все, что вам нужно сделать, – это запустить DFS для графика (учитывая, что ваш график подключен, в противном случае сделать это для всех невидимых вершин) и ЕСЛИ вы найдете соседа узла, который ПОСЕТИЛ, а НЕ родитель, тогда мой друг есть ЦИКЛ на графике, и вы СОВЕРШЕН.

    Вы можете отслеживать родителя, просто передавая родительский параметр, когда вы делаете DFS для своих соседей. И так как вам нужно всего лишь изучить n ребер, сложность времени будет O (n).

    Надеюсь, ответ помог.

    Кстати, если вы знаете, что это связано, то просто это дерево (таким образом, нет циклов) тогда и только тогда, когда |E|=|V|-1 . Конечно, это не маленький объем информации 🙂

    Ответ заключается в том, что в самом деле, сначала поиск по ширине (или поиск по глубине сначала не имеет значения). Детали лежат в анализе.

    Теперь, насколько быстро алгоритм?

    Во-первых, представьте, что график не имеет циклов. Число ребер тогда равно O (V), граф – это лес, цель достигнута.

    Теперь представьте, что график имеет циклы, и ваш алгоритм поиска завершится и сообщит об успехе в первом из них. Граф неориентирован, и, следовательно, когда алгоритм проверяет ребро, есть только две возможности: либо он посетил другой конец ребра, либо он имеет, а затем, это ребро закрывает круг. И как только он видит другую вершину ребра, эта вершина «проверяется», поэтому есть только O (V) этих операций. Второй случай будет достигнут только один раз на протяжении всего алгоритма.

    Я считаю, что предположение о том, что граф связан, может быть немногочисленным. таким образом, вы можете использовать доказательство, показанное выше, что время работы O (| V |). если нет, то | E |> | V |. напоминание: время работы DFS равно O (| V | + | E |) .

    Вот код, который я написал на C на основе DFS, чтобы узнать, связан ли данный граф / циклический или нет. с некоторым количеством выходных данных в конце. Надеюсь, это будет полезно 🙂

     #include #include /****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 

    / * Результат выборки:

     majid@majid-K53SC:~/Desktop$ gcc BFS.c majid@majid-K53SC:~/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! majid@majid-K53SC:~/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! majid@majid-K53SC:~/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! */ 

    Простая DFS выполняет работу по проверке того, имеет ли данный неориентированный граф цикл или нет.

    Вот код C ++.

    Идея, используемая в приведенном выше коде :

    Если узел, который уже обнаружен / посещен, снова найден и не является родительским узлом, тогда у нас есть цикл.

    Это также может быть объяснено ниже (упоминается @ Rafał Dowgird

    Если неисследованный край приводит к предварительному узлу, то график содержит цикл.

    Неориентированный граф ацикличен (т. Е. Лес), если DFS не дает обратных краев. Так как обратные кромки – это те ребра ( u , v ), соединяющие вершину u с предком v в дереве глубины, поэтому никаких задних кромок означает, что есть только ребра дерева, поэтому нет цикла. Поэтому мы можем просто смешать DFS. Если найти задний край, есть цикл. Сложность O(V ) вместо O(E + V ) . Так как если есть задний край, он должен быть найден до того, как увидим |V | четкие ребра. Это связано с тем, что в ациклическом (неориентированном) лесу, |E| ≤ |V | + 1 |E| ≤ |V | + 1 |E| ≤ |V | + 1 .

    Недавно я начал изучать графики. Я написал fragment кода в java, который мог бы определить, имеет ли граф циклы. Я использовал DFT для поиска циклов на графике. Вместо рекурсии я использовал стек для перемещения графика.

    На высоком уровне ДПФ с использованием стека выполняется на следующих этапах

    1. Посетите узел
    2. Если узел не находится в списке посещений, добавьте его в список и нажмите его в верхнюю часть стека
    3. Отметьте узел в верхней части стека как текущий узел.
    4. Повторите выше для каждого соседнего узла текущего узла
    5. Если все узлы были посещены, поп текущий узел из стека

    Я выполнил ДПФ из каждого узла Графа и во время обхода, если я столкнулся с вершиной, которую я посетил ранее, я проверил, имела ли вершина глубина стека больше единицы. Я также проверил, имел ли узел ребро для себя и если между узлами было несколько ребер. Версия стека, которую я изначально написал, была не очень элегантной. Я прочитал псевдокод о том, как это можно сделать, используя рекурсию, и это было аккуратно. Вот реализация Java. Массив LinkedList представляет собой график. с каждым узлом и смежными вершинами, обозначенными индексом массива, и каждый элемент соответственно

     class GFG { Boolean isCyclic(int V, LinkedList[] alist) { List visited = new ArrayList(); 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[] alist, List visited, int parent) { visited.add(vertex); for (Iterator 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; } 

    }

    Вы можете использовать библиотеку ускорителей и циклические зависимости . Он имеет решение для поиска циклов с функцией back_edge .

    Как говорили другие … Глубокий первый поиск разрешит его. В общей глубине первый поиск принимает O (V + E), но в этом случае вы знаете, что граф имеет не более O (V) ребер. Таким образом, вы можете просто запустить DFS, и как только вы увидите, что новый фронт увеличивает счетчик. Когда счетчик достиг V, вам не нужно продолжать, потому что график имеет определенный цикл. Очевидно, это принимает O (v).

    Я считаю, что использование DFS правильно также зависит от того, как вы собираетесь представлять свой граф в коде. Например, предположим, что вы используете смежные списки для отслеживания соседних узлов, и ваш граф имеет 2 вершины и только одно ребро: V = {1,2} и E = {(1,2)}. В этом случае, начиная с вершины 1, DFS будет отмечать ее как ПОСЕТИТЕЛЯ и будет помещать 2 в очередь. После этого он будет поп-вершиной 2, а так как 1 смежна с 2, а 1 – ПОСЕТИЛ, DFS сделает вывод о том, что существует цикл (что неверно). Другими словами, в Undirected графах (1,2) и (2,1) есть одно и то же ребро, и вы должны кодировать таким образом, чтобы DFS не учитывала их разные ребра. Сохранение родительского узла для каждого посещенного узла поможет справиться с этой ситуацией.

    Неориентированный граф без цикла имеет | 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; } 

    Interesting Posts

    Почему вы не можете удалить сразу несколько программ в Windows?

    Можем ли мы перегружать операторы для встроенных типов, таких как int или float?

    Остановить событие comboBox selectedIndexChanged от срабатывания при загрузке формы

    Внедрение Rand

    ASP.NET MVC: пользовательская проверка по DataAnnotation

    Занятая петля в других затягиваниях streamа EDT

    Переход к фоновому изображению CSS3

    Как отправить разрыв строки с помощью curl?

    Как вы получаете текущее время суток?

    Почему объявление переменной требуется внутри цикла for-each в java

    Планировщик задач не разбудит компьютер

    Что является хорошим эквивалентом subprocess.check_call, который возвращает содержимое stdout?

    Возможность перевода электронной почты с Yahoo на GMail с использованием почтового клиента IMAP и ПК

    Реляционные шаблоны проектирования баз данных?

    Проблемы с запуском некоторых приложений на Mac, отсутствие сообщения об ошибке

    Давайте будем гением компьютера.