Может ли кто-нибудь дать ссылку для простого объяснения BFS и DFS с ее реализацией?
Ширина первого поиска и глубины Первый поиск
Ответ 1
Допустим, вам предоставлена следующая структура:
Format: Node [Children] A [B C D] B [E F] C [G] D [] E [] F [] G []
Первый поиск по поиску посещает всех детей node перед посещением их детей. Здесь псевдокод и решение для указанной структуры:
1. Enqueue root node. 2. Dequeue and output. If the queue is empty, go to step 5. 3. Enqueue the dequeued node 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
Сначала поиск по глубине сначала посещает самый низкий уровень (самые глубокие дети) дерева. Существует два типа первого поиска глубины: предварительный заказ и пост-порядок. Это просто отличает, когда вы добавляете node к выходу (когда вы посещаете его, а не оставляете его).
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
Ответ 2
Глубина первого поиска:
Ответ 3
Скажем, у вас есть дерево следующим образом:
Это может немного сбивать с толку, потому что E является потомком A и F, но это помогает проиллюстрировать глубину глубокого поиска вначале. Поиск в глубину ищет дерево, идущее настолько глубоко (отсюда и термин глубина), насколько это возможно. Таким образом, обход слева направо будет A, B, D, F, E, C, G.
Поиск в ширину оценивает всех детей в первую очередь, прежде чем перейти к детям детей. Таким образом, то же дерево будет идти A, B, C, E, D, F, G.
Надеюсь это поможет.
Ответ 4
вы можете найти все на wiki:
ссылка также может быть полезна. если вы хотите, чтобы реализация переходила к: библиотека С++ boost: DFS
Ответ 5
Вот несколько ссылок для проверки:
BFS - это неинформированный метод поиска, целью которого является расширение и исследование всех узлов графа или комбинации последовательностей путем систематического поиска каждого решения. Другими словами, он исчерпывающе просматривает весь график или последовательность, не рассматривая цель, пока не найдет ее.
Формально DFS является неосведомленным поиском, который прогрессирует, расширяя первый дочерний элемент node дерева поиска, который появляется и, таким образом, все глубже и глубже до тех пор, пока не будет найден объект node или пока он не достигнет node, который не имеет детей. Затем поиск возвращается, возвращаясь к последнему node, он не закончил изучение
Они содержат не только хорошие объяснения того, как они реализованы в приложениях, но и псевдо-код алгоритма.
Ответ 6
Ответ 7
обход графика с помощью dfs и bfs.
Ответ 8
Изначальная идея:
получить новую очередь... инициализировать ее с помощью корневого node.... цикла через всю очередь и продолжать удалять элемент из очереди и распечатывать его (или сохранять его и т.д.) и проверять, item имеет детей, если они так нажимают их на очередь и продолжают в цикле, пока вы не пройдете весь сегмент (график)...
Ответ 9
фрагмент с двумя указателями.
void BFS(int v,struct Node **p)
{
struct Node *u;
visited[v-1] = TRUE;
printf("%d\t",v);
AddQueue(v);
while(IsEmpty() == FALSE)
{
v = DeleteQueue();
u = *(p+v-1);
while(u!=NULL)
{
if(visited(u->data -1) == FALSE)
{
AddQueue(u->data);
visited[u->data -1]=TRUE;
printf("%d\t",u->data);
}
u = u->next;
}
}
}
Ответ 10
BFS и DFS применимы ко всем типам графиков. Я объясняю это только для двоичного дерева. BFS посещают каждый node сверху вниз, слева направо. Например, для этого:
1
/ \
7 9
\ / \
8 2 3
BFS дает нам: 1 7 9 8 2 3. DFS сначала посещает глубину каждой ветки. Затем он возвращается к родителям. Вы можете следовать этому неофициальному правилу. Сначала левый ребенок, затем правый ребенок, затем родитель. Но вам нужно начинать с глубины каждой ветки. Например, здесь вы начинаете с 8, так как для 7 нет левого ребенка. Затем вы посещаете родителя 7. Затем будет посещен 1 родительский элемент из 7. Затем вы переходите к правильной ветке. Но на этот раз у него осталось 2 ребенка. Итак, вы посещаете 2 (левый ребенок), затем, правый ребенок 3, а затем 9 своих родителей. Итак, DFS дает нам 8 7 1 2 9 3. Это реализация:
import java.util.ArrayList;
import java.util.List;
public class TreeTraverse {
static class Node{
Node(int data){
this.data = data;
this.left = null;
this.right = null;
this.visited = false;
}
int data;
Node left;
Node right;
boolean visited;
}
public static void main(String[] args) {
//The tree:
// 1
// / \
// 7 9
// \ / \
// 8 2 3
Node node1 = new Node(1);
Node node7 = new Node(7);
Node node9 = new Node(9);
Node node8 = new Node(8);
Node node2 = new Node(2);
Node node3 = new Node(3);
node1.left = node7;
node1.right = node9;
node7.right = node8;
node9.right = node3;
node9.left = node2;
System.out.println("DFS: ");
depthFirstSearch(node1);
System.out.println("\nBFS: ");
breadthFirstSearch(node1);
}
private static void depthFirstSearch(Node node){
if(node.left == null && node.right == null){
System.out.print(node.data+" ");
node.visited = true;
}else if(node.left == null || node.left.visited){
depthFirstSearch(node.right);
System.out.print(node.data+" ");
node.visited = true;
}else{
depthFirstSearch(node.left);
node.visited = true;
System.out.print(node.data+" ");
depthFirstSearch(node.right);
}
}
private static void breadthFirstSearch(Node node){
List<Node> al = new ArrayList<>();
al.add(node);
while(!al.isEmpty()){
node = al.get(0);
if(node.left != null){
int index = al.size();
al.add(index,node.left);
}
if(node.right != null){
int index = al.size();
al.add(index,node.right);
}
System.out.print(al.get(0).data+" ");
al.remove(0);
}
}
}
Надеюсь, это поможет. Если вы хотите клонировать проект, перейдите на страницу https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java. Я надеюсь, что это помогает.
Ответ 11
Прежде всего, BFS и DFS - два способа реализации обхода двоичного дерева. Ширина первого означает обход уровня порядка. У Depth First есть три способа реализовать -,.
Предпочтение:
a. Start with root,
b. mark it visited,
c. go to left node
d. (b) - mark it visited
e. Repeat (c) till there is not any new left node remaining
(We are/might be at leaf node at this point,)
f. Is there any right node available? If yes, go to (a).
Обход порядка Сложность времени O (n) - количество раз, когда каждый node посещается только 1, означает, что сумма равна n раз.
Космическая сложность - Лучший случай: Дерево только левые узлы, O (1) Средний случай: идеальное двоичное дерево - пример, n/2 числа узлов, O (n)