Как обнаружить циклы на графике

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

В этом посте мы предполагаем, что в графе есть узлы, состоящие из символов. Например: А → В → С

  1. Определите необходимые переменные:

2. При выполнении DFS пометьте текущий узел как ПОСЕЩАЕМЫЙ, а затем запустите DFS на его дочерних узлах НЕ ПОСЕЩЕННЫЙ. Если какой-либо дочерний элемент со статусом ПОСЕЩАЕТ найден, установите для hasCycles значение true и вернитесь.

3. Запустите DFS для всех узлов UNVISITED.

См. также:  СУРБД — Введение
Понравилась статья? Поделиться с друзьями:
IT Шеф
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

We use cookies in order to give you the best possible experience on our website. By continuing to use this site, you agree to our use of cookies.
Accept
Privacy Policy