Projeto e Análise de Algoritmos I

Aula 10 - Busca em Grafos (BFS e DFS)

Lucas Nunes Alegre

Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica


Estes slides utilizam conteúdo adaptado da bibliografia da disciplina e também de notas de aula e slides prévios dos professores Bruno Grisci, Rodrigo Machado, André Grahl Pereira, Lucas Nunes Alegre, Marcus Ritt e Luciana Buriol.

Busca em Grafos

Pathfinding

Pathfinding

Algoritmos de Busca em Grafos

Problemas de busca em grafos:

Conectividade: Dado um Grafo G e um nó v, descobrir todos os nós alcançáveis a partir de v.

Caminho Mais Curto: Dado um Grafo G e um nó v, descobrir o caminho mais curto a partir de v para todos os outros nós.

Existem duas estratégias principais para algoritmos de busca em grafos:

  • busca em profundidade / depth-first search (DFS)
  • busca em largura / breadth-first search (BFS)

Buscas em Grafos (Conceitualmente)

G1 =

  1. Buscar em largura (a partir de B)


  1. Buscar em profundidade (a partir de B)


Pergunta: em que ordem os vértices serão alcançados em cada uma das estratégias?


Pergunta: como podemos avaliar o custo desses procedimentos?

Custos em Grafos

Um grafo simples G=(V,E) possui dois parâmetros naturais:

  • |V|= n (número de vértices)
  • |E| = m (número de arestas)

Esses parâmetros (n e m) fazem parte da análise, e dependendo pode não ser muito claro como se relacionam.

Por exemplo, qual seria o melhor custo assintótico: O(m^2) ou O(n^2)?

Observe que há algumas relações já vistas entre n e m:

  • m \leq {n \choose 2} \leq n^2 (em grafos simples)
  • m \geq n-1 (em grafos conexos)

Custo das Representações de Grafos e Dígrafos

Matriz de adjacência

\begin{array}{l|ccccccc} & A & B & C & D & E & F & G\\ \hline A & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ B & 0 & 0 & 0 & 0 & 1 & 1 & 0\\ C & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ D & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ E & 0 & 0 & 1 & 0 & 0 & 1 & 0\\ F & 0 & 0 & 0 & 1 & 0 & 0 & 1\\ G & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{array}

Lista de adjacência (Python)

## Grafo como dicionario
g1 = { 'A' : ['B', 'E'],
       'B' : ['E', 'F'],
       'C' : ['D'],
       'D' : [],
       'E' : ['C','F'],
       'F' : ['D','G'],
       'G' : [] }

  • Como m \leq n^2, o custo O(m+n) nunca é pior que O(n^2), sendo muito melhor para grafos esparsos.

  • Listas são mais eficientes para implementar buscas pelo grafo.

Complexidade: Matriz vs. Lista de Adjacência

Seja n = |V| e m = |E|.

Operação Matriz Lista
Espaço O(n^2) O(n + m)
Verificar aresta (u,v) O(1) O(\deg(u))
Listar vizinhos de v O(n) O(\deg(v))
Inserir aresta O(1) O(1)
Remover aresta O(1) O(\deg(u))

Algoritmo Genérico de Busca em Grafos

Algoritmo Genérico de Busca

  • Dado um grafo G = (V, E) e um vértice fonte s
  • Marca s como explorado e todos os outros vértices como não explorados
  • Enquanto for possível:
    • Escolhe uma aresta e = (u, v), onde u já foi explorado e v ainda não foi explorado.
    • Marca v como explorado.

Algoritmo Genérico de Busca

\begin{algorithmic} \Procedure{Busca-Genérica}{$G : \text{Grafo}, s : \text{Nodo}$} \State Marca $s$ como explorado \While{existir vértice $v$ não explorado} \State Escolhe aresta $(u,v)$ onde $u$ foi explorado e $v$ ainda não foi explorado \State Marca $v$ como explorado \EndWhile \EndProcedure \end{algorithmic}

Correção do Algoritmo Genérico

Afirmação: Ao fim do Algoritmo Genérico, um vértice v é marcado como explorado, se e somente se, existe um caminho entre s e v.

Prova (\Rightarrow): Assuma que o vértice v é marcado explorado. Faremos indução no número de iterações.

  • Caso base: P(0) = s explorado, e s tem um caminho para si mesmo.
  • Hipótese indutiva: Assuma P(n), ou seja, todos os nodos explorados até a iteração n possuem caminho a partir de s.
  • Faremos P(n) \to P(n+1):
    • Na iteração n+1, um nodo v é explorado via aresta (u,v), onde u já estava explorado.
    • Pela hipótese, u tem caminho a partir de s.
    • Concatenando o caminho s \to u com (u,v), obtemos um caminho de s para v.

Correção do Algoritmo Genérico (Cont.)

Afirmação: Ao fim do Algoritmo Genérico, um vértice v é marcado como explorado, se e somente se, existe um caminho entre s e v.

Prova (\Rightarrow): Assuma que existe um caminho entre s e v.

  • Por contradição, assumimos que v não termina marcado como explorado.
  • Como s foi explorado logo de cara e o caminho termina em v (não explorado), deve existir alguma aresta e = (a, b) no caminho s \to v na qual a é explorado e b não é explorado.
  • Mas se há aresta e obedecendo esse critério, o laço de busca do Algoritmo Genérico poderia tê-la escolhido, o que implica que o algoritmo ainda não teria terminado!
  • Contradição. \blacksquare

Busca em Profundidade (DFS)

Visualização

Visualização: BFS vs. DFS - https://www.youtube.com/shorts/1-elk8F8_UM

BFS

BFS vs. DFS

Busca em Profundidade (Iterativa)

Busca em profundidade (DFS) pode ser implementada de forma iterativa:

  • Utilizamos uma pilha para registrar nodos a serem visitados
  • Marcamos nodos como visitados após a inserção na pilha
  • A pilha inicia com o nodo inicial da busca
  • O laço principal roda enquanto a pilha não é vazia
  • Dentro do corpo do laço, removemos o nodo da pilha e o processamos
  • Para cada vizinho não visitado do nodo atual, fazemos a sua inserção na pilha e o marcamos como visitado

Busca em Profundidade (DFS)

\begin{algorithmic} \Procedure{DFS}{$G, s$} \State Marca $s$ como visitado \State $S \gets [s]$ \Comment{Pilha (LIFO)} \While{$S$ não vazia} \State $v \gets S.\text{pop}()$ \For{cada $(v, w) \in E$} \If{$w$ não visitado} \State Marca $w$ como visitado \State Adiciona $w$ a $S$ \EndIf \EndFor \EndWhile \EndProcedure \end{algorithmic}

Busca em Profundidade (Iterativa) em Python

Busca em Profundidade (Iterativa): Exemplo

## Grafo como dicionario
g1 = { 'A' : ['B', 'E'],
       'B' : ['E', 'F'],
       'C' : ['D'],
       'D' : [],
       'E' : ['C','F'],
       'F' : ['D','G'],
       'G' : [] }

Resultado de dfs_iter(g1,'A'):

A E F G D C B

Busca em Profundidade (Recursiva)

Busca em profundidade (DFS) pode ser implementada de forma bem simples por meio de recursão:

  • Utilizamos uma vetor global para registrar nodos que já foram visitados, inicializado com false
  • A rotina principal recebe um grafo e um nó de partida
  • Após processar o nó, marca ele como visitado
  • Para cada vizinho não visitado do nó atual, fazemos uma chamada recursiva para explorá-lo

Busca em Profundidade (Recursiva) em Python

Busca em Profundidade (Recursiva): Exemplo

## Grafo como dicionario
g1 = { 'A' : ['B', 'E'],
       'B' : ['E', 'F'],
       'C' : ['D'],
       'D' : [],
       'E' : ['C','F'],
       'F' : ['D','G'],
       'G' : [] }

Resultado de dfs(g1,'A'):

A B E C D F G

Pergunta: Você consegue justificar por que os nodos são visitados em ordem distinta da versão iterativa?

Busca em Largura (BFS)

Busca em Largura (Níveis)

Breadth-First Search (BFS): Explora a partir de s todos os vértices adicionando vértices em camadas.


BFS (Camadas):

  • L_0 = \{s\}
  • L_1 = todos vértices adjacentes a s
  • L_2 = todos vértices que não pertencem a L_0 ou L_1 e que possuem uma aresta que conecta a um vértice em L_1
  • L_{i+1} = todos vértices que não pertencem a camadas anteriores e que possuem uma aresta que conecta a um vértice em L_i

Busca em Largura (Níveis)

  • Busca em largura pode ser pensada como uma busca em níveis.
  • Um nodo no n-ésimo nível está há uma distância de n arestas da origem.

No grafo de exemplo, temos os seguintes níveis (a partir de ‘A’):

  • 0: A
  • 1: B, E
  • 2: C, F
  • 3: D, G

Busca em Largura (Iterativa)

  • BFS também pode ser implementado de uma forma bastante simples utilizando uma fila.

  • O código é essencialmente idêntico à versão iterativa de DFS, só mudando a estrutura de dados:

    • Pilha / LIFO (inserção na frente, remoção na frente): DFS
    • Fila / FIFO (inserção atrás, remoção na frente): BFS

Busca em Largura (BFS)

\begin{algorithmic} \Procedure{BFS}{$G, s$} \State Marca $s$ como explorado \State $Q \gets [s]$ \Comment{Fila (FIFO)} \While{$Q$ não vazio} \State $v \gets Q.\text{pop}()$ \For{cada $(v, w) \in E$} \If{$w$ não explorado} \State Marca $w$ como explorado \State Adiciona $w$ a $Q$ \EndIf \EndFor \EndWhile \EndProcedure \end{algorithmic}

Busca em Largura (Iterativa) em Python

Busca em Largura (Iterativa): Exemplo

## Grafo como dicionario
g1 = { 'A' : ['B', 'E'],
       'B' : ['E', 'F'],
       'C' : ['D'],
       'D' : [],
       'E' : ['C','F'],
       'F' : ['D','G'],
       'G' : [] }

Resultado de bfs_iter(g1, 'A'):

A B E F C D G

Custo de Operações em Python: dict

Operação Custo
k in d O(1) em média, O(n) no pior caso
d[k] O(1) em média, O(n) no pior caso
d[k] = v O(1) em média, O(n) no pior caso
del d[k] O(1) em média, O(n) no pior caso
Iteração / cópia O(n)


Fonte: https://wiki.python.org/moin/TimeComplexity

Custo de Operações em Python: list

Operação Custo
l[i], l[i] = x, len(l) O(1)
append(x), pop() no fim O(1) amortizado
x in l, iteração O(n)
insert(i, x), pop(i), del l[i] O(n)
l[i:j] O(k)


Fonte: https://wiki.python.org/moin/TimeComplexity

Custo de Operações em Python: collections.deque

Operação Custo
append(x), appendleft(x) O(1)
pop(), popleft() O(1)
len(d) O(1)
extend(t), extendleft(t), rotate(k) O(k)
remove(x) O(n)


Fonte: https://wiki.python.org/moin/TimeComplexity

Árvore Associada à Busca

Árvore Associada à Busca

Árvore de Busca. Dada uma busca (DFS ou BFS) em G a partir de um nó v, construir uma árvore associada a essa busca onde cada nó aponta para o elemento que o alcançou diretamente.

Dígrafo g_1:

dfs_iter(g1, 'A'):

A
E
F
G
D
C
B
Árvore de busca:
  • Isso é facilmente implementado com um dicionário auxiliar parent, preenchido ao inserirmos um nó na estrutura.
  • A raiz da árvore é o nó de origem.

Árvore de busca (DFS iterativa)

Veja a modificação do algoritmo DFS iterativo para construir e retornar a árvore:

Propriedades da Busca em Largura (BFS)

Propriedade dos Níveis: Seja T a árvore resultante da BFS para o grafo G = (V, E) e (x, y) uma aresta qualquer de G:

  • Então, os níveis de x e y na árvore de busca diferem no máximo por 1.

Isto ocorre porque, se a diferença fosse maior (ex: y dois ou mais níveis abaixo de x), no momento em que a BFS visitou os vizinhos de x, o vértice y teria sido colocado na fila logo no nível abaixo de x, limitando a diferença de nível a no máximo 1.

Nível i Nível i+1 Nível i+2 Contradição: y deveria estar no nível i+1! Aresta (x, y) impossível na BFS x y

Complexidade Assintótica das Buscas em Grafos

Complexidade da Busca em Largura (BFS)

Afirmação: O algoritmo BFS tem tempo de execução O(n + m).

Detalhes da Prova:

  • Há no máximo n camadas de busca (uma por nodo).
  • Cada vértice aparece em no máximo uma camada, sendo visitado (removido da fila) exatamente uma vez.
    • Custo O(n) para visitar todos os vértices.
  • Quando visitamos um vértice u, iteramos sobre todos os seus vizinhos, o que requer tempo O(deg(u)).
    • O total de vezes que processamos arestas ao longo do algoritmo é exatamente: \sum_{v \in V} deg(v) = 2m = O(m)
  • Somando os dois custos, temos O(n + m).

Complexidade da Busca em Largura (BFS)

\begin{algorithmic} \Procedure{BFS}{$G, s$} \State Marca $s$ como explorado \Comment{$O(1)$} \State $Q \gets [s]$ \Comment{Fila (FIFO) - $O(1)$} \While{$Q$ não vazio} \Comment{Laço executa $n$ vezes no total} \State $v \gets Q.\text{pop}()$ \Comment{$O(1)$} \For{cada vizinho $w$ de $v$} \Comment{Itera $deg(v)$ vezes por nó, totalizando $O(m)$} \If{$w$ não explorado} \Comment{$O(1)$} \State Marca $w$ como explorado \Comment{$O(1)$} \State Adiciona $w$ a $Q$ \Comment{$O(1)$} \EndIf \EndFor \EndWhile \EndProcedure \end{algorithmic}

Análise Assintótica das Buscas em Grafos

  • As versões iterativas de BFS e DFS utilizando filas e pilhas (respectivamente) possuem custo assintótico O(n+m).
  • Abaixo usaremos estrutura para mencionar a pilha ou fila utilizada:

Detalhamento:

  • Há um processo de iniciação do vetor/dicionário de visitados O(n)
  • A estrutura é inicializada com um elemento inicial, e o laço principal finaliza com a estrutura vazia
  • A cada passada pelo corpo do laço principal, removemos um elemento da estrutura e, ao final, adicionamos elementos
  • O número de elementos adicionados à estrutura corresponde ao número de arestas dos vértices percorridos na busca: no pior caso, O(m)

Pergunta Conceitual

Considere um grafo com quantidade infinita de nós (mas nenhum nó com grau infinito).


P. Qual a diferença de comportamento da DFS e BFS nesse caso?

Implementação: Python

Ver Github da disciplina: https://github.com/BrunoGrisci/projeto-e-analise-de-algoritmos/blob/main/paa1/graph_search.ipynb

?