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.

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.

Exemplo simples da execução do algoritmo

Consideremos o seguinte grafo:

DFS - Grafo do primeiro exemplo

Tenhamos ainda que, em caso de empate entre dois vértices, o algoritmo deve escolher o vértice que vem antes por ordem alfabética. Começaremos no vértice A.

  • Do vértice A, podemos ir apenas para o vértice B. (timestamp 1 a "abrir" A)

  • Do vértice B, podemos ir apenas para o vértice E. (timestamp 2 a "abrir" B)

  • Do vértice E, podemos ir apenas para o vértice D. (timestamp 3 a "abrir" E)

  • Do vértice D, podemos ir para os vértices A e B. Contudo, ambos já foram visitados, pelo que não temos para onde ir, e assim que descobrimos D, trancamo-lo. (timestamp 4 a "abrir" D, timestamp 5 a "fechar" D)

(começa aqui um backtracking, após o "fecho" de um vértice)

  • Do vértice E não temos para onde ir, pelo que o trancamos. (timestamp 6 a "fechar" E)

  • Do vértice B não temos para onde ir, pelo que o trancamos. (timestamp 7 a "fechar" B)

  • Do vértice A não temos para onde ir, pelo que o trancamos. (timestamp 8 a "fechar" A)

Trancámos, então, o vértice onde começámos a procurar - restam, contudo, vértices por explorar. Assim sendo, começamos uma nova procura, desta vez pelo vértice C.

  • Do vértice C, podemos ir apenas para os vértices E e F. Contudo, E já foi visitado, pelo que optamos por ir para F. (timestamp 9 a "abrir" C)

  • Do vértice F não temos para onde ir, pelo que o trancamos. (timestamp 10 a "abrir" F, timestamp 11 a "fechar" F)

  • Do vértice C não temos para onde ir, pelo que o trancamos. (timestamp 12 a "fechar" C)

Aqui, terminamos a procura - não restam vértices por explorar.

A tabela abaixo indica os tempos de descoberta e fecho de cada vértice:

A B C D E F
did_i 1 2 9 4 3 10
fif_i 8 7 12 5 6 11

(Aqui, did_i corresponde ao tempo de descoberta e fif_i ao tempo de fecho)

Ao resolver um exercício de procura DFS, provavelmente optar-se-ia por desenhar algo deste género:

Podíamos ainda, no fim, desenhar a floresta DFS do grafo acima. O conceito será abordado mais abaixo.

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 GG, 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 - Θ(V)\Theta(V)
  • Loop 2 - Θ(V)\Theta(V)
  • Loop 3 - Θ(V+E)\Theta(V + E)

Onde VV é o número de vértices do grafo e EE 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 EE 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 OO - 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, Θ(V+E)\Theta(V + E).

Floresta DFS

Uma árvore DFS corresponde à representação de uma procura DFS pela ordem em que os vértices são descobertos. A raiz da árvore é o vértice inicial. Um vértice pode ter mais do que um filho, caso haja mais que um vértice a ser descoberto a partir dele, mas apenas um pai. O conjunto de árvores DFS de um grafo diz-se uma floresta DFS.

Pode existir mais que uma floresta DFS possível num grafo.

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

Exemplo 1 - Floresta com uma árvore

Exemplo 2 - Floresta com mais do que uma árvore

Exemplo 3 - Variação do exemplo anterior

Podemos, ainda demonstrar que há mais do que uma floresta possível para um dado grafo. Pegando no grafo do exemplo anterior, e fazendo uma DFS diferente (começando, por exemplo, em C):

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.

Exemplo - Tipos de Edges

Pegando no grafo do Exemplo 1 acima:

Nem todas as arestas do grafo estão representadas nesta árvore DFS - estão apenas representadas as arestas "normais" da árvore - tree edges. As restantes arestas são, respetivamente (olhando para o grafo original):

  • AFAF - Forward edge
  • FBFB - Back edge
  • DADA - Back edge
  • DHDH - Cross edge
  • HGHG - Cross edge

Poderiam ser representadas tal que:

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

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

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

  • temos um cross edge de uu para vv caso d(v)<f(v)<d(u)<f(u)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.

Teorema do Caminho Branco

Tendo dois vértices uu e vv, temos que vv é descendente de uu se e apenas se, no momento em que uu é descoberto, existir um caminho de vértices brancos - por descobrir - a ligar uu a vv.

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.

Prova do Lema acima

Vamos ter, portanto, de procurar provar a equivalência apresentada. Provar a implicação da direita para a esquerda é fácil - temos que uma back edge só existe entre parentes diretos, pelo que se esta existir uma back edge (u,v)(u, v), então podemos começar um caminho que parte de uu, chega a vv e volta a uu, estando, portanto, na presença de um ciclo. A parte complicada reside em provar a implicação da esquerda para a direita - se um grafo tem um caminho circular, então a DFS revela uma back edge.

Tenhamos um qualquer caminho circular do tipo (v1,...,vn,v1)(v_1, ..., v_n, v_1). Podemos procurar ordená-lo por ordem crescente de tempo de descoberta - ficaríamos com um caminho (v1,...,vn,v1)(v'_1, ..., v'_n, v'_1). Temos, pelo teorema do caminho branco, que v2,...,vnv'_2, ..., v'_n são todos descendentes de v1v'_1 na floresta DFS - assim sendo, (vn,v1)(v'_n, v'_1) é necessariamente uma back edge.

Ordenação Topológica

Ordenação Topológica

Sequência que contém todos os vértices de um grafo G(V,E)G(V, E) apenas uma vez, tal que se (u,v)E(u, v) \in E, então uu aparece antes de vv na ordem topológica. Devido a esta última propriedade, só podemos realizar ordenações topológicas em grafos acíclicos.

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) é ABCDEFGHABCDEFGH, já que ao escrever os arcos do grafo, estes apontam todos para a frente:

Lema

Se G(V,E)G(V, E) é um DAG (grafo acíclico dirigido) e (u,v)E(u, v) \in E, então vv é fechado antes de uu.

  • Caso d(u)<d(v)d(u) < d(v), então d(u)<d(v)<f(v)<f(u)d(u) < d(v) < f(v) < f(u), logo vv é fechado antes de uu.

  • Caso contrário, então d(v)<f(v)<d(u)<f(u)d(v) < f(v) < d(u) < f(u)*, logo uu é fechado antes de vv.

* podemos afirmá-lo já que, caso contrário, poder-se ia descobrir primeiro vv e depois uu, antes de se fechar vv. Como há um arco de uu para vv, teríamos encontrado um ciclo - o grafo, contudo, é um DAG, acíclico por definição - impossível de acontecer.

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 AA:

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

SCCs - Componentes Fortemente Ligados

SCC

Dado um grafo G(V,E)G(V, E), um conjunto de vértices V\overset{\wedge}{V} diz-se um SCC, componente fortemente ligado, de GG se e apenas se:

  • u,vV,uvvu\forall_{u, v} \in \overset{\wedge}{V}, u \to v \wedge v \to u (por esta última parte entenda-se "há um caminho de uu para vv e um de vv para uu"). Colocando em termos mais simples, escolhendo um vértice qualquer do SCC, podemos criar um caminho que chegue a todos os outros vértices do mesmo SCC.

  • É maximal, isto é, não está contido em nenhum outro SCC - não existe um V\overset{\wedge}{V'} tal que V\overset{\wedge}{V} é um subconjunto seu.

Por exemplo, dado o grafo abaixo:

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

Podemos desenhar um grafo dos componentes.

Grafo dos Componentes

Seja G(V,E)G(V, E) um grafo dirigido. O grafo dos componentes de GG é dado por G(VSCC,ESCC)G(V_{SCC}, E_{SCC}), onde:

  • VSCCV_{SCC} é o conjunto dos SCCs de GG.

  • ESCCE_{SCC} é o conjunto de todas as arestas de GG que ligam um SCC a outro. Colocando a afirmação de forma mais formal, temos {(c1,c2)u,v:uc1vc2(u,v)E}.\{(c_1, c_2) | \exists_{u, v}: u \in c1 \wedge v \in c_2 \wedge (u, v) \in E\}. De realçar que pode haver mais que uma aresta a ligar dois componentes.

O tempo de descoberta de um componente corresponde ao tempo de descoberta do vértice que lhe pertence que é descoberto primeiro. O tempo de fecho de um componente corresponde ao tempo de fecho do vértice que lhe pertence que é fechado por último.

Os componentes de um grafo e os do seu grafo transposto (com todos os arcos no sentido contrário) são necessariamente iguais.

Exemplo - Grafo dos Componentes

Dado o grafo abaixo:

O grafo dos componentes correspondente é dado por:

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

A primeira diz-nos que, dados dois vértices uu e vv de GG, se uu pertence a um SCC C1C_1 e vv pertence a um outro SCC C2C_2, e existe uma aresta u,vu, v, então não pode existir qualquer aresta tal que xC1yC2(y,x)Ex \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, C1C_1 e C2C_2, se temos uma aresta que vai de um qualquer vértice de C1C_1 para um qualquer vértice de C2C_2, então obrigatoriamente f(C1)>f(C2)f(C_1) > f(C_2). A prova encontra-se abaixo.

Prova da segunda propriedade - Grafo dos Componentes

Temos 2 casos em que precisamos de nos focar: d(C1)<d(C2)d(C_1) < d(C_2) e d(C1)>d(C2)d(C_1) > d(C_2).

  • No primeiro caso, descobrimos C1C_1 antes de C2C_2. Seja uu o primeiro vértice de C1C_1 a ser descoberto. No momento em que é descoberto, existe necessariamente (porque temos um caminho de C1C_1 para C2C_2) um caminho de vértices brancos a ligar uu a todos os vértices de C2C_2. Assim sendo, concluímos, pelo Teorema do Caminho Branco, que todos os vértices de C2C_2 são, nesta DFS, descendentes de uu, pelo que o tempo de fecho de C2C_2 é necessariamente menor que o tempo de fecho de uu e, por consequência, que o tempo de fecho de C1C_1.

  • No segundo caso, descobrimos C2C_2 antes de C1C_1. Como, pela propriedade 1, não podemos ter um caminho de C2C_2 para C1C_1, podemos garantir que o tempo de fecho de C2C_2 é anterior ao tempo de descoberta de C1C_1 e, por consequência, anterior ao tempo de fecho de C1C_1.

A propriedade 2 fica, então, provada.

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 é Θ(V+E)\Theta(V + E). A da transposição é Θ(E)\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á Θ(V+E)\Theta(V + E).

Exemplo da aplicação do algoritmo

Tenhamos o grafo abaixo (com DFS inicial já realizada, respetivos tempos de descoberta e de fecho indicados):

Os vértices, por ordem decrescente de tempo de fim, serão então GIJLKHDCFBEAGIJLKHDCFBEA.

O respetivo grafo transposto será o seguinte:

Por fim, a DFS realizada por ordem decrescente dos tempos de fim da DFS inicial é tal que:

Assim sendo, a floresta DFS final é:

Temos 5 árvores na floresta DFS, pelo que temos 5 SCCs. O grafo dos componentes correspondente é, então:

É, 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
Exemplo de Aplicação do Algoritmo

Vamos utilizar um grafo não dirigido, como o seguinte:

O decorrer do algoritmo é:

  • Começamos por explorar SS - tem adjacências RR e WW, pelo que adicionamos esses vértices à queue.
  • Exploramos RR, por ser o próximo vértice da queue, e adicionamos VV (a sua única adjacência) à queue.
  • Exploramos WW, e adicionamos TT e XX à queue.
  • Exploramos VV, que não tem qualquer adjacência, pelo que não se adiciona nada à queue.
  • Exploramos TT, que tem como adjacências XX e UU. XX já foi adicionado à queue por WW, pelo que apenas UU é adicionado.
  • Exploramos XX, que tem como adjacências WW, TT e YY. Todos exceto YY já foram adicionados à queue previamente, pelo que apenas YY é adicionado.
  • Exploramos UU, que não tem adjacências por explorar, pelo que nada é adicionado.
  • Exploramos YY, que não tem adjacências por explorar, pelo que nada é adicionado.

O algoritmo termina aqui. Os números ao lado de cada vértice correspondem à distância do vértice que escolhemos como raiz da BFS, neste caso o vértice SS. A estrutura vertical que podemos observar à esquerda corresponde à fila em que os vértices iam sendo colocados.

Em termos de complexidade (agregada), podemos dizer que o primeiro loop (for) tem complexidade Θ(V)\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 Θ(V+E)\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 é Θ(V+E)\Theta(V + E).

Árvore Breadth-First

Por árvore BF temos um sub-grafo de GG correspondente à travessia BFS por GG a começar num dado vértice vv. A árvore BF a começar num dado vértice vv é 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).