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

Я думаю, что поиск в глубину решает эту проблему. Если неисследованное ребро приводит к ранее посещенному узлу, то граф содержит цикл. Это условие также делает его 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

затем выполнение visit (root_node) вызовет исключение тогда и только тогда, когда есть цикл (изначально все узлы должны быть белыми).

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

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

Решить можно с помощью DFS. Временная сложность: O (n)

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

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

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

2. или достигает своих дочерних элементов, которые находятся на один уровень ниже.

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

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

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

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

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

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

Как быстро работает алгоритм?

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

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

ПОДХОД DFS С УСЛОВИЕМ (родительский! = Следующий узел) Давайте посмотрим на код, а затем разберемся, что происходит:

bool Graph::isCyclicUtil(int v, bool visited[], int parent) 
{ 
    // Mark the current node as visited 
    visited[v] = true; 

    // Recur for all the vertices adjacent to this vertex 
    list<int>::iterator i; 
    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
    { 
        // If an adjacent is not visited, then recur for that adjacent 
        if (!visited[*i]) 
        { 
           if (isCyclicUtil(*i, visited, v)) 
              return true; 
        } 

        // If an adjacent is visited and not parent of current vertex, 
        // then there is a cycle. 
        else if (*i != parent) 
           return true; 
    } 
    return false; 
} 

Приведенный выше код объясняет сам себя, но я попытаюсь объяснить одно условие, т.е. * i! = Parent Здесь, если предположим, что график

1--2

Затем, когда мы находимся в 1 и переходим к 2, родительский элемент для 2 становится 1, и когда мы возвращаемся к 1, поскольку 1 находится в матрице adj 2, тогда, поскольку следующая вершина 1 также является родителем 2, поэтому цикл не будет обнаружен для непосредственный родитель в этом подходе DFS. Следовательно, код работает нормально

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

Вот код, который я написал на 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);

    }

/ * Пример вывода:

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.

Как уже упоминали другие ... Поиск в глубину решит эту проблему. Обычно поиск в глубину занимает 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 сделает вывод, что существует цикл (что неверно). Другими словами, в неориентированных графах (1,2) и (2,1) одно и то же ребро, и вы должны кодировать таким образом, чтобы DFS не считала их разными ребрами. Сохранение родительского узла для каждого посещенного узла поможет справиться с этой ситуацией.

Я начал изучать графики недавно. Я написал фрагмент кода на java, который может определить, есть ли у графика циклы. Я использовал 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;
}

}

Вот простая реализация на C ++ алгоритма, который проверяет, есть ли у графа цикл (ы) за O(n) время (n - количество вершин в Graph). Я не показываю здесь реализацию структуры данных Graph (для краткости). Алгоритмы ожидают, что класс Graph будет иметь общедоступные методы vector<int> getAdj(int v), которые возвращают вершины, смежные с v и int getV(), которые возвращают общее количество вершин. Кроме того, алгоритм предполагает, что вершины Графа пронумерованы от 0 to n - 1.

class CheckCycleUndirectedGraph
{
private:
    bool cyclic;
    vector<bool> visited;

    void depthFirstSearch(const Graph& g, int v, int u) {
        visited[v] = true;
        for (auto w : g.getAdj(v)) {
            if (!visited[w]) {
                depthFirstSearch(g, w, v);
            }
            else if (w != u) {
                cyclic = true;
                return;
            }
        }
    }

public:
    CheckCycleUndirectedGraph(const Graph& g) : cyclic(false) {
        visited = vector<bool>(g.getV(), false);
        for (int v = 0; v < g.getV(); v++) {
            if (!visited[v]){
                depthFirstSearch(g, v, v);
                if(cyclic)
                  break;
            }
        }
    }

    bool containsCycle() const {
        return cyclic;
    }
};

Имейте в виду, что Graph может состоять из нескольких несвязанных компонентов и внутри компонентов могут быть циклы. Показанные алгоритмы обнаруживают циклы и на таких графах.

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

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

}