BFS против DFS
Breadth First Search (также известный как BFS) — это метод поиска, используемый для расширения всех узлов определенного графа. Он выполняет эту задачу путем поиска каждого отдельного решения для изучения и расширения этих узлов (или комбинации последовательностей в них). Как таковой, BFS не использует эвристический алгоритм (или алгоритм, который ищет решение по нескольким сценариям). После того, как все узлы получены, они добавляются в очередь, известную как очередь «первый вошел — первый вышел». Те узлы, которые не были исследованы, «хранятся» в контейнере с пометкой «открытый»; после исследования они переносятся в контейнер с пометкой «закрытый».
Поиск по глубине (также известный как DFS) — это метод поиска, который углубляется в дочерний узел поиска, пока не будет достигнута цель (или пока не будет найден узел без каких-либо других перестановок или «детей»). После того, как цель найдена, поиск возвращается к предыдущему узлу, в котором было найдено решение, повторяя процесс до тех пор, пока все узлы не будут успешно перебраны. Таким образом, узлы продолжают откладываться для дальнейшего поиска — это называется нерекурсивной реализацией.
Характеристиками BFS являются пространственная и временная сложность, полнота, доказательство полноты и оптимальность. Пространственная сложность относится к пропорции числа узлов на самом глубоком уровне поиска. Временная сложность относится к фактическому количеству «времени», используемого для рассмотрения каждого пути узла в процессе поиска. Полнота — это, по сути, поиск, который находит решение в графе, независимо от того, какой это граф. Доказательством полноты является самый мелкий уровень, на котором цель найдена в узле на определенной глубине. Наконец, оптимальность относится к BFS, которая не является взвешенной — это граф, используемый для стоимости единичного шага.
DFS является наиболее естественным выходом, использующим spanning tree — это дерево, составленное из всех вершин и некоторых ребер в неориентированном графе. При таком построении граф делится на три класса: Прямые ребра, указывающие от вершины к дочерней вершине; обратные ребра, указывающие от вершины к предыдущей вершине; и перекрестные ребра, которые не делают ни того, ни другого.
Резюме:
1. BFS ищет каждое решение в графе, чтобы расширить его узлы; DFS зарывается вглубь дочернего узла, пока не будет достигнута цель.
2. Характеристики BFS — это пространственная и временная сложность, полнота, доказательство полноты и оптимальность; наиболее естественным результатом для DFS является охватывающее дерево с тремя классами: прямые ребра, обратные ребра и перекрестные ребра.