Projeto e Análise de Algoritmos I

Aula 11 - Aplicações de Busca em Grafos

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.

Aplicações de Busca em Grafos Simples e Dígrafos

Busca em Grafos: Aplicações

Diversos problemas elementares em grafos simples e dígrafos podem ser eficientemente resolvidos utilizando buscas (DFS ou BFS).

Exemplos:

  • Geração da árvore associada à busca
  • Cálculo de distância
  • Cálculo de rota entre nós
  • Determinar componentes conexos em grafos simples
  • Determinar se um grafo simples é bipartido
  • Determinar ordenamento topológico em dígrafos acíclicos
  • Determinar componentes fortemente conexos em dígrafos
  • Determinar a existência de ciclos

Árvore de 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)

Cálculo de Distância em Grafo Não-Valorado

Cálculo de Distância

Cálculo de Distância. Dado um grafo simples ou dígrafo G e um nodo v, determinar um vetor de distâncias de v para todos os nodos de G.

BFS já fornece a distância:

  • Se um dado nodo x é alcançável a partir de v, ele vai aparecer em algum dos níveis: o nível é a respectiva distância.
  • Se não for alcançável, a distância é infinita.

Implementação:

  • Inicia-se um vetor com valor 0 em v (e infinito nos demais nodos)
  • Ao inserir um nodo na lista, atribui a este a distância do nodo pai (que o inseriu) + 1.

Observações:

  • DFS não pode ser utilizada para cálculo de distância. Por quê?
  • Assumimos que G não possui pesos nas arestas.

Distância em Grafos e Dígrafos

Outras Variações de Rota e Distância

Conectividade. Dado um grafo simples ou dígrafo G e dois nodos a e b, determinar se a está conectado a b.

Solução: Iniciar busca (DFS ou BFS) em a, comparando o nodo atual com b. Se achar, retorna True. Se a busca terminar sem achar b, retorna False.

Rota entre Nodos. Dado um grafo simples ou dígrafo G e dois nodos a e b, determinar uma rota iniciando em a e terminando em b.

Solução: Iniciar busca (DFS ou BFS) em a produzindo a árvore de busca. Ao achar b, a rota entre a e b é a inversão do caminho de b até a na árvore de busca.

Rota com Menor Número de Arestas. Dado um grafo simples ou dígrafo G e dois nodos a e b, determinar uma rota com o menor número de arestas entre a e b.

Solução: Como no caso de rota, porém utilizando exclusivamente BFS.

Componentes Conexos

Aplicação: Flood Fill (Paint)

  • Uma aplicação prática comum baseada em detecção de componentes conexos é a ferramenta “balde de tinta” ou Flood Fill.
  • No modelo de grafos para esse problema:
    • Nodos: os pixels de uma imagem.
    • Arestas: conectam pixels adjacentes que possuem a mesma cor.
    • Componente Conexo: corresponde a uma determinada região/área da imagem de cor homogênea contígua.
  • O algoritmo busca a partir de um vértice e recolore toda a região percorrida.

Componentes Conexos em Grafos Simples (UCC)

Componentes Conexos (UCC). Dado um grafo simples G, determinar o número de componentes conexos e quais os nós contidos em cada um (Undirected Connected Components).

  • Como as arestas em grafos simples são bidirecionais, basta iniciar em um nó a e coletar todos os nós alcançáveis a partir dele para obter o componente conexo que contém a.
  • Podemos usar um vetor de componentes para marcar a qual componente cada nodo pertence.
  • Para calcular todos os componentes de um grafo:
    • Escolhemos um nó arbitrário e por meio de busca determinamos o componente ao qual pertence.
    • Após, escolhemos outro nó e repetimos até que todos os nós do grafo tenham sido percorridos.

Componentes Conexos em Grafos Simples (UCC)

Componentes Conexos em Grafos: Exemplo

Teste de Bipartição

Teste de Bipartição

Teste de Bipartição. Dado um grafo simples G, determinar se G é bipartido (isto é, se seus vértices podem ser particionados em dois conjuntos independentes V_1 e V_2, ou equivalentemente, se não possui ciclos ímpares).

Conforme visto, um grafo é bipartido se e somente se não possuir ciclos ímpares. Esta caracterização nos fornece um algoritmo bastante eficiente baseado em coloração de nodos e BFS para testar bipartição.

  • Defina um vetor cor que associa true (cor 1) ou false (cor 0) a cada nodo.
  • Para cada componente do grafo, escolha um nodo e pinte com cor 1. Inicie uma busca em largura na qual todos os nodos alcançáveis a partir de um dado nodo precisam ser pintados com a cor oposta.
  • Se em algum momento detectarmos que um nodo já pintado possui cor idêntica àquela do nodo atual (vizinho com a mesma cor), retornamos falso (detecção de ciclo ímpar). Se conseguirmos concluir a coloração de todos os nodos, retornamos true.

Teste de Bipartição: Código

Ordenamento Topológico

Ordenamento Topológico

Ordenamento Topológico. Dado um dígrafo acíclico (DAG) G = (V, E), encontrar uma sequência linear v_1, v_2, \ldots, v_n contendo todos os vértices de V tal que, para toda aresta direcionada (v_i, v_j) \in E, o vértice origem v_i precede o vértice destino v_j na sequência (isto é, i < j).

Exemplo:

Alguns possíveis ordenamentos topológicos para G_5:

  • A, G, B, H, I, C, D, F, E
  • G, H, I, A, B, F, C, D, E

Algoritmo de Kahn para Ordenamento Topológico

Algoritmo de Kahn (1962) para ordenamento topológico:

  • Um nodo de grau de entrada zero é seguro para iniciar o ordenamento
  • Ao remover ele do grafo (e suas arestas de saída), podem-se gerar novos nodos de grau zero
  • Podemos pré-calcular o grau de entrada de todos os nós (armazenando em um vetor inDeg) e iniciar uma lista q contendo nodos de grau zero a serem processados
  • Removemos um nodo x de q e colocamos no final do ordenamento gerado
  • Após, decrementamos o grau de todos os nós alcançáveis por x: se o grau de um deles chegar a zero, o inserimos em q. Repita até esgotar q.

Algoritmo de Kahn para Ordenamento Topológico: Código

Ordenamento Topológico com DFS

Busca em profundidade (DFS) também pode ser utilizada para determinar ordenamento topológico.

  • Inserção no Topo:
    • Um nodo v só é inserido na lista pos após o retorno de todas as chamadas recursivas de DFS geradas por ele.
    • Ao usar pos.insert(0, v), garantimos que as dependências apareçam antes de seus sucessores na lista final.
  • Garantia de Cobertura:
    • O laço principal percorre todos os nodos do grafo, garantindo que mesmo componentes desconexas sejam processadas.
  • Resultado:
    • A lista final é uma ordenação linear onde, para toda aresta (u \to v), o nodo u precede v.

Ordenamento Topológico (DFS, Lista de Nodos)

Componentes Fortemente Conexos

Componentes Fortemente Conexos (SCC)

Componentes Fortemente Conexos (SCC). Dado um dígrafo G = (V, E), decompor V em componentes fortemente conexos (Strongly Connected Components), onde cada componente é um subdígrafo conexo maximal no qual todo par de vértices é mutuamente alcançável.

Diferentemente de grafos simples, por conta da direcionalidade dos arcos, pode haver mais de um componente mesmo que o dígrafo pareça estar “em um único pedaço”.

Componentes fortemente conexos (nodos):

  • [1, 3, 5]
  • [11]
  • [6, 8, 10]
  • [2, 4, 7, 9]

Componentes Fortemente Conexos (SCC) (Cont.)

Componentes: [1, 3, 5], [11], [6, 8, 10], [2, 4, 7, 9]

  • Uma busca a partir de um nodo qualquer pode nos dar mais do que o SCC que o contém (por conta da direcionalidade)
  • Iniciando em 11 obtemos [11, 6, 8, 10], em 10 obtemos [6, 8, 10], e em 1 obtemos todos os nodos
  • Se comprimíssemos cada SCC em um único nodo, o grafo obtido dos componentes seria acíclico. Por quê?
  • Se iniciarmos uma busca em um componente sumidouro (sink), i.e., um componente com grau de saída igual a 0, obtemos somente os nodos deste (e de mais nenhum outro componente)
  • Pergunta: Mas como identificamos os nodos de um sumidouro?

Algoritmo de Kosaraju-Shamir (SCC)

Kosaraju (e Shamir, independentemente) descobriram que, ao rodar ordenamento topológico sobre um dígrafo arbitrário (não necessariamente acíclico), temos que o primeiro nodo do ordenamento obrigatoriamente pertence a um componente fonte (source).

  • Porém, observe que precisamos de um nodo do sumidouro, não da fonte!

Solução: toposort sobre o grafo reverso (G^R)! Isso gera uma sequência de nodos que pode ser usada para guiar uma busca por componentes no grafo original que nunca inclui mais do que o componente atual de cada nodo.

Algoritmo de Kosaraju-Shamir (SCC)

Detecção de Ciclos

Detecção de Ciclos

Detecção de Ciclos. Dado um grafo simples, pseudografo ou dígrafo G, determinar a existência de ciclos (se G contém pelo menos um ciclo).


Há diferenças importantes entre os modelos com arcos unidirecionais ou bidirecionais:

  • Em um grafo simples, os menores ciclos são triângulos;
  • Em um dígrafo, um loop ou um par de arcos de ida e volta configuram ciclo;
  • Em um pseudografo, um loop ou arestas paralelas configuram ciclo.

Detecção de Ciclos em Grafos Simples (DFS)

Ideia principal: Para cada componente conexo (nó ainda não visitado), iniciamos uma busca em profundidade (DFS) e mantemos o nó pai de cada vértice.


  • Como o grafo é não-direcionado, cada aresta aparece duas vezes (uma em cada direção). Assim, ao explorar um vértice, devemos ignorar a aresta que leva de volta ao seu pai.


  • Durante a busca, se encontrarmos um vizinho já visitado que não seja o pai do vértice atual, então detectamos um ciclo.


  • Repita o processo para todos os vértices ainda não visitados (componentes conexos).

Detecção de Ciclos em Dígrafos (Kahn)

Ideia principal: Rodar o algoritmo de ordenamento topológico de Kahn sobre o dígrafo (baseado em graus de entrada).


  • Se houver ciclos, isso impede que os nós do ciclo em questão obtenham grau de entrada 0 e possam ser inseridos na solução.


  • Isto é, o algoritmo vai listar um ordenamento com menos vértices do que o total de vértices do grafo se o grafo contém algum ciclo.

Conclusão

Moral da Aula

Podemos usar DFS e BFS para resolver diversos problemas em grafos simples e dígrafos de forma eficiente.


Complexidade Linear: \Theta(|V| + |E|)

?