Busca em Grafo

Vamos falar de duas maneiras de se fazer busca num grafo, a Busca em Largura (BFS) e Busca em Profundidade (DFS).
Para facilitar, vamos usar um grafo com lista de adjacência seguindo essa implementação:

typedef vector<vector<int> > grafo;

O funcionamento de ambas é muito parecido, diferindo apenas na ordem em que visitam os vértices por causa da estrutura auxiliar que usam para definir as próximas visitas.

BUSCA EM LARGURA

BFS (Breadth-First Search ou Busca em Largura) é uma busca que se faz da seguinte maneira:

• Criamos uma fila de vértices a serem visitados, inicialmente vazia
• Colocamos um vértice inicial v qualquer na fila para iniciar a busca
• Enquanto existem vértices na fila, removemos o primeiro vértice da fila e adicionamos todos os seus adjacentes nela
• Repetimos o passo acima até que todos tenham sido visitados.

O que vai acontecer é que os níveis do grafo vão sendo visitados um por um:

Isso ocorre porque os vértices são postos numa fila, ou seja, a prioridade de visita é de quem é adicionado antes.

Esse tipo de busca é útil quando queremos encontrar vértices mais próximos do vértice de origem mais rapidamente.

int mark[100000];                       //array para marcar quem já foi visitado

void BFS(grafo G, int v){               //v é o vértice inicial
    memset(mark, 0, sizeof(mark));      //desmarcamos todos os vértices inicialmente
    queue<int> fila;                    //criamos uma fila vazia
    fila.push(v);                       //inserimos o vértice inicial nela

    while(fila.size()){                 //enquanto há elementos na fila
        v = fila.front();               //v recebe o primeiro elemento
        fila.pop();                     //eliminamos o primeiro elemento
        if(!mark[v]){                   //se v não está marcado ainda
            printf("%d ", v);
            mark[v] = 1;                               //marca v
            for(int i = 0; i < G[v].size(); i++)       //coloca os adjacentes de v
                fila.push(G[v][i]);                    //na fila
        }
    }
}

//teste BSF

int main(){
    #define pb push_back                 /*       1        */
    grafo G(10);                         /*      /|\       */
    G[1].pb(2); G[1].pb(3); G[1].pb(4);  /*     / | \      */
    G[2].pb(5);                          /*    2  3  4     */
    G[3].pb(6); G[3].pb(7);              /*   /  / \  \    */
    G[4].pb(8);                          /*  5  6   7  8   */
    G[6].pb(9);                          /*     |          */
    BFS(G, 1);                           /*     9          */
}

BUSCA EM PROFUNDIDADE

DFS (Depth-First Search ou Busca em Profundidade) é uma busca que se faz da seguinte maneira:

• Criamos uma pilha de vértices a serem visitados, inicialmente vazia
• Colocamos um vértice inicial v qualquer na pilha para iniciar a busca
• Enquanto existem vértices na pilha, removemos o primeiro vértice da pilha e adicionamos todos os seus adjacentes nela
• Repetimos o passo acima até que todos tenham sido visitados.

O que vai acontecer é que a busca vai tentar descer o máximo possível:

Isso ocorre porque os adjacentes são postos numa pilha e ganham prioridade imediata, ou seja, a prioridade de visita é dos adjacentes do último vértice que foi visitado.

Esse tipo de busca é útil quando queremos procurar os vértices mais distantes do vértice de origem mais rapidamente.

int mark[100000];

void DFS(grafo G, int v){
    memset(mark, 0, sizeof(mark));
    stack<int> pilha;
    pilha.push(v);                   //principal mudança, aqui é uma pilha

    while(pilha.size()){
        v = pilha.top();
        pilha.pop();
        if(!mark[v]){
            printf("%d ", v);
            mark[v] = 1;
            for(int i = 0; i < G[v].size(); i++)
                pilha.push(G[v][i]);
        }
    }
}

//teste DFS
int main(){
    #define pb push_back                 /*       1        */
    grafo G(10);                         /*      /|\       */
    G[1].pb(2); G[1].pb(4); G[1].pb(8);  /*     / | \      */
    G[2].pb(3);                          /*    2  4  8     */
    G[4].pb(5); G[4].pb(7);              /*   /  / \  \    */
    G[5].pb(6);                          /*  3  5   7  9   */
    G[8].pb(9);                          /*     |          */
    DFS(G, 1);                           /*     6          */
}

A ordem não fica igual à da animação abaixo porque na implementação, colocamos os filhos na pilha do primeiro até o último, logo o 8 seria visitado antes do 2. Se quisermos mudar isso, basta olharmos os filhos de trás pra frente. Para fazer essa alteração, basta mudar o for para for(int i = G[v].size() - 1; i >= 0; i--), fazendo isso, olhamos os adjacentes de trás pra frente e a ordem bate com a animação.





Eis uma comparação entre o funcionamento de ambas as buscas:




No pior caso, podemos considerar que as buscas vão olhar todos os vértices e todas as arestas, então sendo V o número de vértices e E o número de arestas:

 Complexidade da BFS e DFS: O(V + E)  

As buscas em grafo tem diversas aplicações, como por exemplo:

• Encontrar menor caminho entre vértices
• Saber se o grafo é bipartido
• Achar árvore geradora de peso mínimo (MST ou Minimum Spanning Tree)
• Encontrar ciclos no grafo
• Saber se um grafo é conexo
• Fazer Topological Sort

entre outras.