TOP 25 ALGORITMOS | Depth First Search (DFS)
- #Estrutura de dados
O algoritmo começa de uma fonte dada e explora todos os vértices alcançáveis da fonte dada. Em um grafo (tipo de estrutura de dados), pode haver loops. Então usamos um array visitado extra para garantir que não processemos um mesmo vértice novamente.
📁 | Resumo
🤖 | Código
function dfsRec(adj, visited, s){
// Marcar o vértice atual como visitado
visited[s] = true;
// Imprima o vértice atual
process.stdout.write(s + " ");
// Visita recursivamente todos os vértices adjacentes que ainda não foram visitados
for (let i of adj[s]) {
if (!visited[i]) {
dfsRec(adj, visited, i);
}
}
}
function dfs(adj, s){
const visited = new Array(adj.length).fill(false);
// Chamar a função DFS recursiva
dfsRec(adj, visited, s);
}
function addEdge(adj, s, t){
// Adicione a aresta do vértice s ao t
adj[s].push(t);
// Devido ao gráfico não direcionado
adj[t].push(s);
}
const V = 5; // Número de vértices no gráfico
// Crie uma lista de adjacências para o gráfico
const adj = Array.from({length : V}, () => []);
// Defina as arestas do gráfico
const edges =
[ [ 1, 2 ], [ 1, 0 ], [ 2, 0 ], [ 2, 3 ], [ 2, 4 ] ];
// Preencha a lista de adjacências com arestas
for (let e of edges) {
addEdge(adj, e[0], e[1]);
}
🕰️ | Complexidade de Tempo
A complexidade depende do número de vértices (V) e de arestas (A) do grafo, sendo portanto, O(V+A).
📦 | Complexidade de Espaço
A complexidade depende do número de vértices (V) e de arestas (A) do grafo, sendo portanto, O(V+A).
.
Obs.: lembre que este algoritmo necessita da utilização de um espaço auxiliar!
✔️ | Vantagens
✦ A busca é limitada pelo tempo;
✦ Requisição linear de memória;
❌ | Desvantagens
✦ Um grafo finito pode gerar uma solução infinita;