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

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

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

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

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

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

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

1 - 2

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

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