Определение цикла

Описание

Общая информация

Циклы в ненаправленных графах

Циклы в направленных графах

В теории графов два типа объектов обычно называются циклами.

Один тип циклов, чаще называющиеся замкнутым обходом, состоит из последовательности вершин, начинающейся и заканчивающейся в той же самой вершине, и каждые две последовательные вершины в последовательности смежны. Другой тип циклов, иногда называемых простыми циклами, - это замкнутые обходы без повторного прохода по ребру или посещения вершины дважды, за исключением начальной и конечной вершин. Простые циклы можно описать набором ребер, в отличие от замкнутых обходов, в которых наборы ребер (с возможным повторением) не определяют однозначно порядок вершин. Ориентированный цикл в ориентированном графе - это последовательность вершин, начинающаяся и завершающаяся в той же самой вершине, и в этой последовательности для любых двух последовательных вершин существует дуга из более ранней в более позднюю. Такое же различие между простыми циклами и обходами, как выше, можно определить и для ориентированных графов.

Граф с окрашенными ребрами для иллюстрации пути H-A-B, замкнутого пути или обхода с повторением вершин B-D-E-F-D-C-B и цикла без повторения ребер или вершин H-D-G-H

Поиск цикла

Неориентированный граф имеет цикл в том и только в том случае, когда поиск в глубину (DFS) находит ребро, которое приводит к уже посещенной вершине (обратная дуга). Таким же образом, все обратные ребра, которые алгоритм DFS обнаруживает, являются частями циклов. Для неориентированных графов требуется только время O(n) для нахождения цикла в графе с n вершинами, поскольку максимум n − 1 ребер могут быть ребрами дерева.

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

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

Определение цикла в неориентированном графе

Реализация

Цикл в ненаправленном графе можно обнаружить, как минимум, двумя способами.

С помощью поиска в глубину (DFS):

// algorithms/graphs/detect-cycle/undirected.js
import depthFirstSearch from '../depth-first-search'

// Функция принимает граф
export default function detectUndirectedCycle(graph) {
  let cycle = null

  // Список посещенных узлов
  const visited = {}

  // Список предков каждого посещенного узла
  const parents = {}

  // Обработчики для DFS
  const callbacks = {
    // Обработчик вхождения в узел
    enterNode: ({ currentNode, previousNode }) => {
      // Если узел уже посещен, то обнаружен цикл
      if (visited[currentNode.getKey()]) {
        // Вычисляем его путь
        cycle = {}

        let current = currentNode
        let previous = previousNode

        while (currentNode.getKey() !== previous.getKey()) {
          cycle[current.getKey()] = previous
          current = previous
          previous = parents[previous.getKey()]
        }

        cycle[current.getKey()] = previous
      } else {
        // Добавляем текущий узел в посещенные
        visited[currentNode.getKey()] = currentNode
        // Обновляем список предков
        parents[currentNode.getKey()] = previousNode
      }
    },
    // Обработчик определения допустимости обхода
    allowTraverse: ({ currentNode, nextNode }) => {
      // Запрещаем обход цикла
      if (cycle) {
        return false
      }

      // Запрещаем возвращаться к предку
      const currentNodeParent = parents[currentNode.getKey()]

      return currentNodeParent?.getKey() !== nextNode.getKey()
    },
  }

  // Берем первый узел
  const startNode = graph.getAllNodes()[0]
  // Запускаем поиск в глубину
  depthFirstSearch(graph, startNode, callbacks)

  return cycle
}

Тесты

С помощью системы непересекающихся множеств (disjoint set):

// algorithms/graphs/detect-cycle/undirected-disjoint-set.js
import DisjoinSet from '../../../data-structures/disjoint-set'

export default function detectUndirectedCycleUsingDisjointSet(graph) {
  // Создаем непересекающиеся одноэлементные множества для каждого узла графа
  const keyExtractor = (node) => node.getKey()
  const disjointSet = new DisjoinSet(keyExtractor)
  graph.getAllNodes().forEach((node) => disjointSet.makeSet(node))

  // Перебираем все ребра графа и проверяем, что узлы ребра принадлежат
  // разным множествам. В этом случае объединяем множества. Делаем это
  // до обнаружения узлов, которые принадлежат обоим множествам. Это
  // означает обнаружение цикла
  let cycle = false
  graph.getAllEdges().forEach((edge) => {
    if (disjointSet.isSameSet(edge.from, edge.to)) {
      cycle = true
    } else {
      disjointSet.union(edge.from, edge.to)
    }
  })

  return cycle
}

Тесты

Определение цикла в ориентированном графе

Алгоритм определения цикла в направленном графе также можно реализовать с помощью поиска в глубину (DFS):

// algorithms/graphs/detect-cycle/__tests__/directed.test.js
import depthFirstSearch from '../depth-first-search'

export default function detectDirectedCycle(graph) {
  let cycle = null

  // Список предков каждого посещенного узла
  const parents = {}

  // Белый набор содержит узлы, которые еще не посещались
  const whiteSet = {}

  // Серый набор содержит узлы, которые посещаются сейчас (на текущем пути)
  const graySet = {}

  // Черный набор содержит узлы, которые полностью посещены.
  // Это означает, что были посещены все потомки узла
  const blackSet = {}

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

  // Инициализируем белый набор
  graph.getAllNodes().forEach((node) => {
    whiteSet[node.getKey()] = node
  })

  // Обработчики для DFS
  const callbacks = {
    // Обработчик вхождения в узел
    enterNode: ({ currentNode, previousNode }) => {
      // Если узел находится в сером наборе, значит, обнаружен цикл
      if (graySet[currentNode.getKey()]) {
        // Вычисляем его путь
        cycle = {}

        let current = currentNode
        let previous = previousNode

        while (currentNode.getKey() !== previous.getKey()) {
          cycle[current.getKey()] = previous
          current = previous
          previous = parents[previous.getKey()]
        }

        cycle[current.getKey()] = previous
      } else {
        // Добавляем текущий узел в серый набор и удаляем его из белого набора
        graySet[currentNode.getKey()] = currentNode
        delete whiteSet[currentNode.getKey()]

        // Обновляем список предков
        parents[currentNode.getKey()] = previousNode
      }
    },
    // Обработчик выхода из узла
    leaveNode: ({ currentNode }) => {
      // Если все потомки узла были посещены, удаляем его из серого набора
      // и добавляем в черный набор
      blackSet[currentNode.getKey()] = currentNode
      delete graySet[currentNode.getKey()]
    },
    // Обработчик определения допустимости обхода
    allowTraverse: ({ nextNode }) => {
      // Запрещаем обход цикла
      if (cycle) {
        return false
      }

      // Запрещаем обход черных узлов
      return !blackSet[nextNode.getKey()]
    },
  }

  // Пока в белом наборе есть узлы
  while (Object.keys(whiteSet).length) {
    // Берем первый узел
    const firstKey = Object.keys(whiteSet)[0]
    const startNode = whiteSet[firstKey]
    // Запускаем поиск в глубину
    depthFirstSearch(graph, startNode, callbacks)
  }

  return cycle
}

Тесты

Запускаем тесты:

npm run test ./algorithms/graphs/detect-cycle/__tests__

Определение цикла в неориентированном графе​

Определение цикла в ориентированном графе​

Определение цикла в неориентированном графе

Определение цикла в ориентированном графе