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