При запуске DFS мы можем легко проверить наличие циклов, отслеживая статус каждого узла. Изначально все узлы будут помечены как НЕ ПОСЕЩЕННЫЕ. Когда начинается обход узла, мы отмечаем его как ПОСЕЩЕНИЕ, а когда мы закончим с узлом, мы отмечаем его как ПОСЕЩЕНИЕ. Таким образом, когда мы обходим дочерние элементы узла, мы можем проверить, имеет ли дочерний элемент статус В ПОСЕЩЕНИИ, если такой дочерний элемент есть, то граф имеет циклы. Это связано с тем, что только предки дочернего узла будут помечены как посещающие, поэтому, если мы найдем узел со статусом посещения, мы можем быть уверены, что он указывает на одного из своих предков (и, следовательно, на цикл).
В этом посте мы предполагаем, что в графе есть узлы, состоящие из символов. Например: А → В → С
- Определите необходимые переменные:
2. При выполнении DFS пометьте текущий узел как ПОСЕЩАЕМЫЙ, а затем запустите DFS на его дочерних узлах НЕ ПОСЕЩЕННЫЙ. Если какой-либо дочерний элемент со статусом ПОСЕЩАЕТ найден, установите для hasCycles значение true и вернитесь.
3. Запустите DFS для всех узлов UNVISITED.