DEV Community

Mateus Vinícius
Mateus Vinícius

Posted on

Criando um algoritmo de pesquisa em largura em grafos

Grafos são estruturas de dados que consistem em vértices (ou nós) conectados por arestas (ou arcos). Eles são amplamente utilizados em várias áreas, como ciência da computação, matemática, física, biologia, entre outras.

Na ciência da computação, por exemplo, os grafos são usados para representar relações entre objetos, como usuários em uma rede social, ou para modelar rotas e caminhos em mapas, como as ruas no Google Maps. Eles permitem a análise de dados complexos, possibilitando a descoberta de padrões e informações úteis. Vejamos o seguinte grafo:

Grafo com as seguintes vértices: A, B, C, D, E e F

Para responder perguntas como "existe um caminho do vértice A ao vértice B?" ou "qual é o caminho mínimo do vértice A ao vértice B?", uma das soluções é utilizar o algoritmo de pesquisa em largura (BFS - breadth-first search). Ele começa no vértice A e expande sua pesquisa para os vértices conectados a ele, que são B e C. Em seguida, avança para os vértices conectados a B e C, e assim por diante, buscando em largura.

Vamos criar um exemplo de algoritmo de pesquisa em largura usando JavaScript, para responder a seguinte questão: Qual o caminho mais curto do vértice A ao vértice F?

Primeiro vamos definir as vértices e suas conexões como um objeto:

const connections = {
    A: [ 'B', 'C' ],
    B: [ 'A', 'D', 'F' ],
    C: [ 'A', 'D', 'E' ],
    D: [ 'B', 'C' ],
    F: [ 'B', 'E' ],
    E: [ 'C', 'F' ]
}
Enter fullscreen mode Exit fullscreen mode

Estamos dizendo que A se conecta com B e C, que B se conecta com A, D e F e assim sucessivamente.

Agora vamos começar a criar nosso algoritmo. Primeiro precisamos que ele faça um loop por todos os vértices do grafo e identifique quais já foram visitados.

function findShortestPath(graph, startNode, endNode) {
    // fila dos vertices que serão visitados
    const queue = [startNode];
    // objeto contendo os vértices que já foram visitados
    const visited = { [startNode]: true };
    // objeto que vai identificar quais os vértices anteriores a um determinado vértice pra montarmos o caminho
    const predecessor = {};

    // Loop enquanto houverem vértices para ser visitados
    while (queue.length) {
        // Obtém e remove o primeiro vértice da lista
        const currNode = queue.shift();

        // RESTO DO NOSSO ALGORITMO
    }

    return null;
}
Enter fullscreen mode Exit fullscreen mode

Agora precisamos fazer com que, a cada novo vértice buscado, a função obtenha o vértice anterior que se ligue a ele e adicione o caminho no nosso objeto predecessor.

function findShortestPath(graph, startNode, endNode) {
    const queue = [startNode];
    const visited = { [startNode]: true };
    const predecessor = {};

    while (queue.length) {
      const currNode = queue.shift();
      // Obtém os vértices que estão conectados ao vértice atual
      // aqui são chamados de vizinhos
      const neighbors = graph[currNode];

      // Itera sobre cada vértice vizinho
      for (const neighbor of neighbors) {

        // Apenas continua a busca se ele ainda não tiver sido visitado
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            // Adiciona no objeto predecessor o vértice que está ligado a ele
            predecessor[neighbor] = currNode;
            // Adiciona ele mesmo na fila de vértices para serem pesquisados
            queue.push(neighbor);

            // RESTO DO NOSSO ALGORITMO
        }
      }
    }


Enter fullscreen mode Exit fullscreen mode

Agora que o algoritmo já busca todos os vértices do nosso grafo, precisamos fazer com que ele obtenha o vértice de destino e, a partir do objeto predecessor, construa o caminho de volta ao ponto inicial.

function findShortestPath(graph, startNode, endNode) {
    const queue = [startNode];
    const visited = { [startNode]: true };
    const predecessor = {};

    while (queue.length) {
      const currNode = queue.shift();
      const neighbors = graph[currNode];

      for (const neighbor of neighbors) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          predecessor[neighbor] = currNode;
          queue.push(neighbor);

          // Observa se o vizinho que está sendo checado atualmente...
          // é o nosso destino
          if (neighbor === endNode) {
            // Começa a reconstruir o caminho mais curto a partir do vértice...
            // de chegada
            const shortestPath = [endNode];
            // Obtém o vértice atual de onde os vizinhos foram obtidos
            let prevNode = currNode;

            // Loop enquanto o caminho ainda não tiver sido reconstruído...
            // até o ponto de partida
            while (prevNode !== startNode) {
                // Adiciona no começo da array `shortestPath` o vértice `prevNode`
                shortestPath.unshift(prevNode);
                // Obtém o predecessor do `prevNode` e faz dele o `prevNode` atual
                prevNode = predecessor[prevNode];
            }

            shortestPath.unshift(startNode);
            return shortestPath;
          }
        }
      }
    }

    return null;
}
Enter fullscreen mode Exit fullscreen mode

Ao executar o nosso código vemos o resultado da busca:

const connections = {
    A: [ 'B', 'C' ],
    B: [ 'A', 'D', 'F' ],
    C: [ 'A', 'D', 'E' ],
    D: [ 'B', 'C' ],
    F: [ 'B', 'E' ],
    E: [ 'C', 'F' ]
}

const shortestPath = findShortestPath(connections, 'A', 'F');

console.log(shortestPath); // ['A', 'B', 'F']
Enter fullscreen mode Exit fullscreen mode

Podemos ver que o caminho mais curto do vértice ao vértice F de fato é A -> B -> F:

Imagem que mostra os vértices A, B e F conectados em destaque

O algoritmo de busca em largura é uma ferramenta essencial na resolução de problemas que envolvem a descoberta do menor caminho entre dois pontos em um grafo. Mas é importante lembrar que cada aplicação pode ter suas particularidades e o algoritmo de pesquisa em largura não é o único e pode não ser o melhor algoritmo de busca pelo menor caminho em muitos casos.

Saber implementar um algoritmo de pesquisa em largura pode ajudar a solucionar problemas complexos em diversas áreas, como redes de transporte, otimização de rotas e até mesmo jogos.

Top comments (0)