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;