Caminhos mais curtos em grafos não pesados
Problema: dado um grafo $G=(V,E)$ (não pesado) e um vértice $u\in V$, queremos determinar o cominho mais curto de $u$ para todos os outros vértices.
Tal como vimos na última aula, no final de uma BFS sobre $G$ a partir $u$, o vector d contém o custo do caminho mais curto de $u$ para todos os outros vértices $v\in V$, i.e., d[u] $= \delta(u,v)$. Para determinar o caminho mais curto de $u$ até $v$ basta portanto utilizar o vector de predecessores pi também calculado pela BFS e reconstruir o caminho andando para trás desde $v$ até $u$.
Árvores abrangentes
Problema: dado um grafo $G=(V,E)$ ligado com $n$ vértices queremos determinar uma árvore abrangente em $G$, ou seja, um sub-grafo $T$ ligado de $G$ com $n-1$ arcos e sem ciclos (dado dois vértices, apenas existe um caminho entre os mesmos em $T$).
Neste caso podemos utilizar quer a BFS quer a DFS, em que a árvore BFS e a árvore DFS (existe apenas uma porque o grafo é ligado) correspondem a uma árvore abrangente para $G$. Notar que pode existir (e por norma existem) mais do que uma árvore abrangente para $G$.
Ordenação topológica
Problema: dado um grafo orientado e acíclico $G=(V,E)$ queremos determinar uma ordenação dos vértices de $G$ tal que, para qualquer arco $(u,v)\in E$, $v$ aparece após $u$ na ordenação.
Consideremos uma DFS sobre $G$. A primeira observação é que, uma vez que o grafo é acíclico, nunca podemos ter arcos para trás, ou seja, arcos que durante a visita liguem a um predecessor do vértice em que estamos na árvore DFS. Por outro lado, se existe um caminho de $u$ para $v$ em $G$, temos que os tempos de fim de $u$ e $v$ são tais que f[u] $>$ f[v]. Logo, basta ordenar os vértices de forma decrescente dos tempos de fim para obtermos uma ordenação topológica.
Notar que podemos obter várias ordenações igualmente válidas para um mesmo grafo $G$, ou seja, a ordenação topológica para $G$ pode não ser única. Todas as DFS dão origem a uma ordenação topológica, e todas as ordenações topológicas podem ser explicadas por pelo menos uma DFS.
Exemplo:
Componentes conexos e componentes fortemente conexos em grafos
Problema: dado um grafo orientado $G=(V,E)$ queremos determinar todos os conjuntos máximos de vértices $C$ tais que, se $u,v\in C$, então existe um caminho de $u$ para $v$ em $G$ e existe um caminho de $v$ para $u$ em $G$.
Existem vários algoritmos para resolver este problema, em que o algoritmo de Tarjan é provavelmente o mais conhecido. Aqui vamos utilizar uma algoritmo alternativo que utiliza duas DFS e, para tal, precisamos da noção de grafo transposto.
Dado um grafo orientado $G=(V,E)$, o grafo transposto $G'$ de $G$ é tal que $G'=(V,E')$ com $E' = \{(v,u)\ |\ (u,v)\in E\}$. Dado $G$ podemos determinar facilmente $G'$ em tempo $O(V+E)$.
Algoritmo para determinar as SCCs (Strongly Connected Components):
- executar uma DFS sobre $G$ e guardar os tempos de fim para cada vértice;
- transpor $G$ obtendo $G'$;
- executar uma DFS sobre $G'$ considerando no ciclo principal os vértices por ordem decrescente dos tempos de fim calculados em 1.
O conjunto de vértices de cada árvore na floresta resultante da última DFS corresponde a uma SCC. Se associarmos a cada SCC um vértice e se criarmos um novo grafo em que adicionamos os arcos que ligam SCCs diferentes, então obtemos o grafo de componentes que é necessariamente acíclico (porquê?). O algoritmo corre em tempo $O(V+E)$.
Explicação:
Exemplo, incluindo o respectivo grafo de componentes à direita:
Exercícios
Exercício 1: Proponha um algoritmo para determinar se um grafo $G=(V,E)$ é bipartido, ou seja, se os vértices de $G$ podem ser divididos em dois conjuntos disjuntos $L$ e $R$ tais que, para qualquer $(u,v)\in E$, temos que $u\in L$ e $v\in R$, ou $u\in R$ e $v\in L$.
Exercício 2: Proponha um algoritmo para determinar o número total de caminhos possíveis entre qualquer par de vértices num grafo orientado e acíclico $G=(V,E)$.
Exercício 3: Implemente o algoritmo para determinar componentes fortemente ligados por forma a retornar no final o grafo de componentes sem arcos múltiplos.