Почему DFS и не BFS для нахождения цикла в графиках

Я не знаю, почему такой старый вопрос открылся в моем канале, но все предыдущие ответы плохи, таким образом...

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

В DFS, каждую вершину "посещают", где посещение вершины означает:

1. вершина запускается

2. , подграф, достижимый от той вершины, посещают. Это включает трассировку всех непрослеженных краев, которые достижимы от той вершины, и посещающий все достижимые непосещаемые вершины.

3. вершина закончена.

критическая функция - то, что все края, достижимые от вершины, прослежены, прежде чем вершина закончена. Это - функция DFS, но не BFS. На самом деле это - определение DFS.

из-за этой функции, мы знаем это, когда первый вершина в цикле запускается:

1. Ни один из краев в цикле не был прослежен. Мы знаем это, потому что можно только добраться до них от другой вершины в цикле, и мы говорим о первый вершина, которая будет запущена.
2. Все непрослеженные края, достижимые от той вершины, будут прослежены, прежде чем она будет закончена, и что включает все края в цикл, потому что ни один из них еще не был прослежен. Поэтому, если будет цикл, то мы найдем край назад к первой вершине после того, как это будет запущено, но прежде чем это будет закончено; и
3. , Так как все края, которые прослежены, достижимы от каждой started-unfinished вершины, находя, что край к такой вершине всегда указывает на цикл.

Так, если будет цикл, то мы, как гарантируют, найдем край к started-unfinished вершине (2), и если мы находим такой край, тогда нам гарантируют это существует цикл (3).

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

BFS не обеспечивает таких гарантий, таким образом, он просто не работает. (несмотря на совершенно хорошие находящие цикл алгоритмы, которые включают BFS или подобный как подпроцедура)

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

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

BFS может быть разумным, если граф неориентированный (будьте добры показать эффективный алгоритм, использующий BFS, который бы сообщал о циклах в направленном графе!), где каждое "поперечное ребро" определяет цикл. Если поперечное ребро - {v1, v2}, а корень (в дереве BFS), содержащий эти узлы - r, то цикл - r ~ v1 - v2 ~ r (~ - путь, - - одиночное ребро), о чем можно сообщить почти так же просто, как в DFS.

Единственная причина использовать BFS - это если вы знаете, что ваш (неориентированный) граф будет иметь длинные пути и небольшое покрытие путей (другими словами, глубокий и узкий). В этом случае BFS потребует пропорционально меньше памяти для своей очереди, чем стек DFS (оба варианта, конечно, все еще линейны).

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

Если вы поместите цикл в случайное место на дереве, DFS будет иметь тенденцию попадать в цикл, когда он покрывает примерно половину дерева, причем половину времени он уже прошел там, где идет цикл, и в половине случаев он не будет (и найдет его в среднем в половине остальной части дерева), поэтому он будет оценивать в среднем примерно 0,5 * 0,5 + 0,5 * 0,75 = 0,625 дерева.

Если вы поместите цикл в случайное место на дереве, BFS будет иметь тенденцию попадать в цикл только тогда, когда он оценивает слой дерева на этой глубине. Таким образом, вам обычно приходится оценивать листья двоичного дерева баланса, что обычно приводит к оценке большей части дерева. В частности, в 3/4 случаев хотя бы одна из двух ссылок появляется в листьях дерева, и в этих случаях вам нужно оценить в среднем 3/4 дерева (если есть одна ссылка) или 7 / 8 дерева (если их два), так что вы уже ожидаете поиска 1/2 * 3/4 ​​+ 1/4 * 7/8 = (7 + 12) / 32 = 21/32 = 0,656 ... дерева, даже не добавляя стоимости поиска в дереве с циклом, добавленным от конечных узлов.

Кроме того, DFS проще реализовать, чем BFS. Поэтому его следует использовать, если вы ничего не знаете о своих циклах (например, циклы, скорее всего, будут находиться рядом с корнем, из которого вы выполняете поиск, и в этот момент BFS дает вам преимущество).

Поиск в глубину более эффективен с точки зрения памяти, чем поиск в ширину, поскольку вы можете вернуться назад. Это также проще реализовать, если вы используете стек вызовов, но это зависит от самого длинного пути, не выходящего за пределы стека.

Также, если ваш граф направлен , то вам нужно не только помнить, посещали ли вы узел или нет, но и как вы туда попали. В противном случае вы можете подумать, что нашли цикл, но на самом деле все, что у вас есть, - это два отдельных пути A-> B, но это не значит, что существует путь B-> A. Например,

Если вы выполните BFS, начиная с 0 , он определит, что цикл присутствует, но на самом деле цикла нет.

При поиске в глубину вы можете отмечать узлы как посещенные при спуске и снимать отметки при возврате. См. Комментарии о повышении производительности этого алгоритма.

Для лучшего алгоритма обнаружения циклов в ориентированном графе вы можете посмотреть алгоритм Тарьяна .