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

Question

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

Answer 1

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

Answer 2

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

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

Answer 3

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

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

Answer 4

Вы можете решить это, используя DFS. Временная сложность: O (n)

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

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

1. Каждый из них достигает своего единственного родителя, который на один уровень выше его.

2.или достигают своих детей, которые на один уровень ниже его.

Таким образом, если у узла есть какое-либо другое ребро, которого нет среди двух, описанных выше, он, очевидно, соединит узел с одним из его предков, отличным от его родителя. Это сформирует ЦИКЛ.

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

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

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

Answer 5

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

Answer 6

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

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

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

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

Answer 7

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

Answer 8

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

На DFT высокого уровня использование стека выполняется в следующих шагах

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

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

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;
}

}

Answer 9

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

Answer 10

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

Вот код C ++ к тому же.

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

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

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

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