TOP 25 ALGORITMOS | Breadth First Search (BFS)

O algoritmo começa de uma fonte dada e explora todos os vértices alcançáveis ​​da fonte dada. Como a árvore, começamos com a fonte dada (na árvore, começamos com a raiz) e atravessamos os vértices nível por nível usando uma estrutura de dados de fila. O único problema aqui é que, diferentemente das árvores, os gráficos podem conter ciclos, então podemos chegar ao mesmo nó novamente. Para evitar processar um nó mais de uma vez, usamos um array booleano visitado.

📁 | Resumo

🤖 | Código

function bfs(adj, s) {
  const visited = Array(V).fill(false); 
  const queue = []; 


  // Marca o nó de origem como visitado e o enfileira
  visited[s] = true;
  queue.push(s);


  // Itera sobre a fila
  while (queue.length) {
  
      // Desfila um vértice da fila e o imprime
      const curr = queue.shift();
      process.stdout.write(curr + " ");


      // Obtém todos os vértices adjacentes do vértice desenfileirado. Se um adjacente não foi visitado, marca-o como visitado e o enfileira
      for (const x of adj[curr]) {
          if (!visited[x]) {
              visited[x] = true;
              queue.push(x);
          }
      }
  }
}


// Função para adicionar uma aresta ao gráfico
function addEdge(u, v) {
  adj[u].push(v);
  adj[v].push(u);
}

🕰️ | 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), sendo portanto, O(V).

✔️ | Vantagens

✦ Nunca ficará preso em looping;

✦ Se houver uma solução, o algoritmo irá encontrar;

✦ Se houver mais de uma solução, o algoritmo pode irá encontrar a mais eficiente;

❌ | Desvantagens

✦ É limitado pelo uso de memória;