Поиск в ширину и поиск в глубину
Кто-либо может дать ссылку для простого объяснения на BFS и DFS с его реализацией?
7 ответов
Допустим, вам дана следующая структура:
Format: Node [Children] A [B C D] B [E F] C [G] D [] E [] F [] G []
Поиск в ширину посещает все дочерние узлы перед посещением их дочерних узлов. Вот псевдокод и решение для вышеупомянутой структуры:
1. Enqueue root node. 2. Dequeue and output. If the queue is empty, go to step 5. 3. Enqueue the dequeued node's children. 4. Go to Step 2. 5. Done
Two queues: (Active Node) [Output] [Working Set] Starting with root: ( ) [] [A] (A) [A] [B C D] (B) [A B] [C D E F] (C) [A B C] [D E F G] (D) [A B C D] [E F G] (E) [A B C D E] [F G] (F) [A B C D E F] [G] (G) [A B C D E F G] [] Done
Поиск в глубину сначала посещает самый нижний уровень (самые глубокие дочерние элементы) дерева. Существует два типа поиска в глубину: предварительный заказ и пост-заказ. Это просто различает, когда вы добавляете узел к выходу (когда вы его посещаете, а не оставляете его).
var rootNode = structure.getRoot();
var preOrder = new Array();
var postOrder = new Array();
function DepthFirst( rootNode ){
// Pre-order
preOrder[ preOrder.length ] = rootNode;
for( var child in rootNode ){
DepthFirst( child );
}
// Post-order
postOrder[ postOrder.length ] = rootNode;
}
Pre-order: * A B E F C G D Post-order: * E F B G C D A
Допустим, у вас есть дерево следующего вида:
Это может немного сбивать с толку, потому что E является потомком A и F, но это помогает проиллюстрировать глубина в поиске в глубину. Поиск в глубину сначала исследует дерево настолько глубоко (отсюда и термин «глубина»), насколько это возможно. Таким образом, обход слева направо будет A, B, D, F, E, C, G.
Поиск в ширину сначала оценивает всех дочерних элементов, прежде чем перейти к дочерним элементам. Таким образом, это же дерево будет идти A, B, C, E, D, F, G.
Надеюсь, это поможет.
вы можете найти все на вики:
эта ссылка тоже может быть полезной. Если вам нужна реализация, перейдите в: Библиотека повышения c ++: DFS
Вот несколько ссылок, на которые стоит обратить внимание:
BFS - это неинформированный метод поиска, цель которого - расширить и изучить все узлы графа или комбинации последовательностей путем систематического поиска каждого решения. Другими словами, он тщательно просматривает весь граф или последовательность, не учитывая цель, пока не найдет ее.
Формально, DFS - это неинформированный поиск, который прогрессирует, расширяя первый дочерний узел появляющегося дерева поиска и, таким образом, углубляясь все глубже и глубже, пока не будет найден целевой узел или пока он не достигнет узла. у которого нет детей. Затем поиск возвращается к самому последнему узлу, который он еще не изучил
. Они не только содержат хорошие объяснения того, как они реализованы в приложениях, но также содержат некоторый псевдокод алгоритма.
