Diferença entre BFS e DFS Diferença entre
Breadth First Search (também conhecido como BFS) é um método de pesquisa usado para ampliar todos os nós de um gráfico particular. Ele realiza essa tarefa pesquisando todas as soluções para examinar e expandir esses nós (ou uma combinação de seqüências). Como tal, um BFS não usa um algoritmo heurístico (ou um algoritmo que busca uma solução através de vários cenários). Depois que todos os nós são obtidos, eles são adicionados a uma fila conhecida como a fila First In, First Out. Os nós que não foram explorados são "armazenados" em um recipiente marcado como "aberto"; Uma vez explorados, eles são transportados para um recipiente marcado como "fechado".
A primeira pesquisa de profundidade (também conhecida como DFS) é um método de busca que se aprofunda em um nó filho de uma pesquisa até atingir um objetivo (ou até que haja um nó sem quaisquer permutações ou ' crianças'). Depois que um objetivo é encontrado, a pesquisa retrocede para um nó anterior que foi com uma solução, repetindo o processo até que todos os nós tenham sido pesquisados com sucesso. Como tal, os nós continuam a ser postos de lado para uma exploração mais aprofundada - isso é chamado de implementação não recursiva.
Os recursos do BFS são complexidade do tempo e espaço, completude, prova de integridade e otimização. A complexidade do espaço refere-se à proporção do número de nós no nível mais profundo de uma pesquisa. A complexidade do tempo refere-se à quantidade real de "tempo" usado para considerar cada caminho que um nó usará em uma pesquisa. A integridade é, essencialmente, uma pesquisa que encontra uma solução em um gráfico, independentemente do tipo de gráfico que seja. A prova da completude é o nível mais raso no qual um objetivo é encontrado em um nó em uma profundidade definida. Finalmente, a otimização refere-se a um BFS que não é ponderado - esse é um gráfico usado para custo unit-step.
Um DFS é a saída mais natural usando uma árvore de expansão - que é uma árvore composta de todos os vértices e algumas bordas em um gráfico não direcionado. Nesta formação, o gráfico é dividido em três classes: bordas diretas, apontando de um nó para um nó filho; bordas traseiras, apontando de um nó para um nó anterior; e bordas transversais, que não fazem nenhum desses.
Resumo:
1. Um BFS procura cada solução em um gráfico para expandir seus nós; um DFS mergulha profundamente dentro de um nó filho até atingir um objetivo.
2. As características de um BFS são complexidade do espaço e do tempo, completude, prova de integridade e otimização; a saída mais natural para um DFS é uma árvore abrangente com três classes: bordas dianteiras, bordas traseiras e bordas transversais.
