image

Access unlimited bootcamps and 650+ courses forever

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

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

    image

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

    Share
    Comments (1)

    MS

    Meri Silva - 13/11/2024 15:18

    Interessante mais muito complicado para entender!