image

Access unlimited bootcamps and 650+ courses forever

60
%OFF
Article image
Isadora Ariane
Isadora Ariane13/11/2024 14:14
Share

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

image

🤖 | 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;

Share
Comments (0)