Algoritmos Elementares sobre Grafos

Vamos procurar rever e aprofundar conceitos previamente abordados em IAED, tais como DFS (incluindo ordenação topológica e componentes fortemente ligados) e BFS.

DFS - Depth First Search

Consiste num algoritmo recursivo que utiliza a noção de backtracking. Procura esgotar todos os caminhos possíveis em frente, voltando para trás quando já não há mais possibilidades de seguir em frente.

No algoritmo que estudámos em aula, cada vértice do grafo tem algumas propriedades que facilitam o desenrolar da DFS:

• cada vértice tem um pai, pi, inicialmente nulo (Nil, no pseudocódigo), que corresponde ao seu predecessor na procura.

• cada vértice tem uma cor - White, Gray ou Black. Um vértice é White antes de ser descoberto, Gray entre descoberta e fecho, e Black quando está fechado.

• cada vértice tem um tempo de descoberta e um tempo de fecho.

Tendo como argumento um grafo $G$, o pseudocódigo do algoritmo da DFS pode ser tal que:

// every graph G has a set of vertices V
DFS(G)
  for v in G.V // loop 1
    v.color = White
    v.discovery = 0
    v.closure = 0
    v.pi = Nil
  time := 0
  for v in G.V // loop 2
    if v.color == White
      DFS_Visit(G, v)

DFS_Visit(G, v)
  time = time + 1
  v.discovery = time
  v.color = Gray
  for w in G.Adj[v] // loop 3
    if w.color == White
      w.pi = v
      DFS_Visit(G, w)
  time = time + 1
  v.closure = time
  v.color = Black

As complexidades temporais (agregadas - durante todo o decorrer do algoritmo) de cada loop acima são:

• Loop 1 - $\Theta(V)$
• Loop 2 - $\Theta(V)$
• Loop 3 - $\Theta(V + E)$

Onde $V$ é o número de vértices do grafo e $E$ o número de arcos/arestas.

A complexidade do primeiro loop é trivial, o loop é claramente executado apenas uma vez para cada vértice. A do segundo também segue a mesma lógica, sendo executado uma vez para cada vértice. A do terceiro não é óbvia. Temos cada, para cada vértice, DFS_Visit é chamada apenas uma vez (porque assim que deixa o estado White, não volta a poder ter esse estado). Além disso, para cada vértice, o loop é executado $E$ vezes, uma vez para cada arco/aresta que liga aquele vértice a outro. Isto, claro, considerando todo o decorrer do algoritmo - foi assim que a complexidade do algoritmo foi abordada em aula.

Resta ainda realçar que foi utilizado $\Theta$ e não $O$ - os loops, aqui, são executados exatamente com aquela complexidade, sempre, qualquer que seja o grafo-argumento do algoritmo.

A complexidade temporal total do algoritmo é, portanto, $\Theta(V + E)$.

Temos, abaixo, dois exemplos de grafos com respetivas florestas DFS:

Podemos, na floresta DFS, representar vários tipos de arcos (arcos estes que representam arcos do próprio grafo):

• Tree edges - as arestas "normais" da árvore, consecutivas, de nó em nó.

• Forward edges - arestas "para a frente", não consecutivas.

• Back edges - arestas "para trás", não consecutivas.

• Cross edges - arestas "cruzadas". Ao contrário das outras arestas, estas não correspondem a descendentes/ascendentes diretos - podemos pensar nelas como relações entre primos, tios, etc.

Em termos de tempos de descoberta, para cada tipo de aresta, temos que (tendo dois vértices, $u$ e $v$):

• temos um tree ou um forward edge de $u$ para $v$ caso $d(u) < d(v) < f(v) < f(u)$.

• temos um back edge de $u$ para $v$ caso $d(v) < d(u) < f(u) < f(v)$.

• temos um cross edge de $u$ para $v$ caso $d(v) < f(v) < d(u) < f(u)$.

Antes de abordar a ordenação topológica e os componentes fortemente ligados, é relevante enunciar o Teorema do Caminho Branco.

Podemos, ainda, provar que um grafo tem um caminho circular se e apenas se a DFS revela um arco para trás. A prova encontra-se abaixo.

Ordenação Topológica

Segundo o professor, para resolver exercícios associados a ordenação topológica, pode dar jeito desenhar o grafo na horizontal, como pode ser observado abaixo:

Podemos, aqui, admitir que uma ordenação topológica possível (não a única) é $ABCDEFGH$, já que ao escrever os arcos do grafo, estes apontam todos para a frente:

Uma ordenação topológica pode, então, ser dada pela ordem decrescente de tempos de fecho de uma DFS a um dado grafo. Por exemplo, dado o grafo abaixo e respetiva DFS a começar em $A$:

A ordenação topológica via ordem decrescente de tempos de fecho é dada por $GDEHABFC$. Podemos, claro, confirmar que não há back edges (para confirmar que a ordenação topológica está feita corretamente):

SCCs - Componentes Fortemente Ligados

Por exemplo, dado o grafo abaixo:

Temos dois SCCs - $ABC$ e $D$. $D$ não pertence a $ABC$ porque, apesar de ser possível construir um caminho de $D$ para $ABC$, o contrário não se verifica.

Podemos desenhar um grafo dos componentes.

Os grafos dos componentes gozam de um par de propriedades interessantes.

A primeira diz-nos que, dados dois vértices $u$ e $v$ de $G$, se $u$ pertence a um SCC $C_1$ e $v$ pertence a um outro SCC $C_2$, e existe uma aresta $u, v$, então não pode existir qualquer aresta tal que $x \in C_1 \wedge y \in C_2 \wedge (y, x) \in E$ - caso contrário, nenhum dos componentes seria maximal, já que poderíamos fazer caminhos entre todos os vértices de ambos os componentes em questão. Esta propriedade permite-nos, ainda, afirmar que o grafo dos componentes é um DAG, necessariamente.

A segunda diz-nos que, tendo dois SCCs, $C_1$ e $C_2$, se temos uma aresta que vai de um qualquer vértice de $C_1$ para um qualquer vértice de $C_2$, então obrigatoriamente $f(C_1) > f(C_2)$. A prova encontra-se abaixo.

O algoritmo para chegar aos SCCs de um grafo é bastante simples:

• Fazer uma DFS normal, guardando uma lista com os vértices ordenada de modo decrescente pelos respetivos tempos de fim.
• Transpor o grafo - alterar o sentido de todos os seus arcos.
• Fazer outra DFS (ao grafo transposto), seguindo desta vez a ordem decrescente que guardámos no primeiro passo. A ordem decrescente é relevante ao escolher a raiz do caminho, mas aquando da exploração do caminho em si, não importa - podemos escolher qualquer vértice.

Cada árvore da floresta DFS do grafo transposto corresponderá a um SCC do grafo original.

A complexidade temporal de ambas as DFS é $\Theta(V + E)$. A da transposição é $\Theta(E)$ (considerando que a representação das arestas é feita através de uma lista de adjacências). Assim, a complexidade temporal do algoritmo como um todo será $\Theta(V + E)$.

BFS - Breadth First Search

É, tal como a DFS, um algoritmo para travessia de grafos. Se na DFS o objetivo prendia-se em percorrer os caminhos em profundidade, até eventualmente ter de voltar para trás (backtracking), na BFS o objetivo passa por percorrer os caminhos em largura. Utiliza a noção de fila (vulgo queue) para guardar os vértices a serem explorados num futuro próximo. O próximo vértice a ser explorado é sempre o que está no início da fila. De realçar ainda que utilizamos uma fila regular, do tipo FIFO, first in first out.

Começamos na raiz, com a fila inicialmente vazia, e vamos adicionando os vértices adjacentes ao vértice atual à fila. Fazemo-lo sucessivamente, extraindo sempre o primeiro elemento da fila e repetindo o processo até a fila estar vazia - quando estiver, a procura está concluída.

O pseudocódigo do algoritmo é o seguinte:

BFS(G, v) // v é o vértice-raiz da procura
  for each n in V except v
    n.color = white
    n.distance = inf // inicialmente a infinito
    n.pi = nil
  v.color = gray
  v.distance = 0
  v.parent = nil
  Q := new queue
  Q.enqueue(v)
  while Q is not empty
    u := Q.dequeue()
    for each n in Adj(u)
      if n.color == white
        n.color = gray
        n.distance = u.distance + 1
        n.pi = u
        Q.enqueue(n)
    u.color = black

Em termos de complexidade (agregada), podemos dizer que o primeiro loop (for) tem complexidade $\Theta(V)$ (passa por todos os vértices menos um, sem operações recursivas no seu interior), enquanto que o segundo loop (while) tem complexidade $\Theta(V + E)$, já que a queue irá incluir todos os vértices, e para cada vértice são verificadas todas as suas adjacências. Podemos, assim, admitir que a complexidade temporal da BFS é $\Theta(V + E)$.

Árvore Breadth-First

Por árvore BF temos um sub-grafo de $G$ correspondente à travessia BFS por $G$ a começar num dado vértice $v$. A árvore BF a começar num dado vértice $v$ é igual a uma árvore DFS a começar no mesmo vértice - os vértices atingíveis a partir de uma fonte são sempre os mesmos, os "tempos" em que descobrimos cada vértice na procura é que podem ser diferentes.

Por exemplo, para a BFS:

A árvore BF correspondente é a abaixo:

As "distâncias" (os tempos indicados na BFS) correspondem a níveis da árvore (como se pode ver acima).

• Notas DFS - Prof. José Fragoso
• Notas SCCs e BFS - Prof. José Fragoso
• Notas sobre DFS - Universidade de Edimburgo