Lesson24

Algumas propriedades simples em grafos são fáceis de determinar, independentemente da ordem pela qual se examinam os arcos, como é o caso do grau de todos os vértices. Outras propriedades estão associadas a caminhos, pelo que se torna necessário identificá-las através de pesquisa feita de vértice em vértice ao longo dos arcos. A maioria dos algoritmos em grafos que vamos estudar utilizam este modelo abstracto básico e torna-se então necessário analisar o essencial dos algoritmos de procura em grafos e suas propriedades estruturais.

Procurar em grafos é equivalente a percorrer labirintos e, em particular, é necessário marcar os pontos já visitados e deverá ser possível recuar, num caminho efectuado, até ao ponto de partida. Os vários algoritmos de procura em grafos limitam-se a executar uma determinada estratégia de procura em labirintos.

A procura em profundidade primeiro (DFS – Depth-First Search) admite duas implementações, recursiva e com uso de pilha explícita. Substituindo a pilha por uma fila FIFO, passamos a ter uma procura em largura primeiro (BFS – Breadth-First Search).

Dado um vértice origem/fonte, a procura consite em geral em visitar todos os vértices atingíveis a partir da origem, ou seja, todos os vértices que estão em qualquer caminho do grafo que comece na origem. A ordem pela qual os vértices são visitados depende do tipo de procura.

Procura em largura primeiro / Breadth-First Search (BFS)

Numa BFS visitamos os vértices por ordem da sua distância à origem, ou seja, os vértices mais próximos são visitados em primeiro lugar. Vértices não atingíveis a partir da origem não são visitados.

Dados $G=(V,E)$ e um vértice fonte $s\in V$, numa BFS exploramos sistematicamente os vértices de $G$ para descobrir todos os vértices atingíveis a partir de $s$ e, durante a procura temos:

• O cálculo da distância: menor número de arcos de $s$ para cada vértice atingível.
• A identificação da árvore BF: caminho mais curto de $s$ para cada vértice atingível $v$.
• Que fronteira entre os nós descobertos e não descobertos é expandida uniformemente.
• Que os vértices à distância $k$ são descobertos antes de qualquer vértice à distância $k+1$.

Aplicações

1. Encontrar as componentes conexas de um grafo.
2. Encontrar todos os vértices de uma componente conexa.
3. Encontrar todos os caminhos mais curtos entre 2 vértices, $u$ e $v$, num dado grafo (não pesado ou, pelo menos, não considerando os pesos).

Implementação

• color[v]: cor do vértice $v$:
  • branco: não visitado;
  • cinzento: já visitado mas pelo menos um dos vértices adjacentes não foi visitado ou a procura em pelo menos um dos vértices adjacentes não foi terminada;
  • preto: já visitado e a procura nos vértices adjacentes já está terminada.
• pi[v]: predecessor de $v$ na árvore BF;
• d[v]: tempo de descoberta de $v$ (o tempo de descoberta para o vértice fonte é 0).

Implementação em que utilizamos uma fila:

void bfs(Graph G, int s)
{
  int u, v;

  for (u = 0; u < G->V; u++) {
    color[u] = WHITE;
    d[u] = -1;
    p[u] = -1;
  }

  color[s] = GRAY;
  d[s] = 0;
  QUEUEput(s);
  
  while (!QUEUEempty()) {
    u = QUEUEget();
    for (v = 0; v < G->V; v++)
      if (G->adj[u][v] == 1) {
        if (color[v] == WHITE) {
          color[v] = GRAY;
          d[v] = d[u] + 1;
          p[v] = u;
          QUEUEput(v);
        }
      }
    color[u] = BLACK;
  }
}

Exercício: Implementar para grafos representados com listas de adjacências em vez de matriz de adjacências.

Exemplo

Complexidade

O tempo de execução da BFS depende da representação utilizada para os grafos. No caso da matriz de adjacências temos $O(V^2)$:

• a inicialização corre em tempo $O(V)$;
• cada vértice é colocado na fila apenas 1 vez, $O(V)$;
• cada linha da matriz é visitada 1 vez por cada vértice, portanto $O(V^2)$.

No caso das listas de adjacências temos $O(V + E)$:

• a inicialização corre em tempo $O(V)$;
• cada vértice é colocado na fila apenas 1 vez, $O(V)$;
• a lista de adjacências é visitada 1 vez por cada vértice, portanto $O(E)$ no total.

Análise

Denota-se por $\delta(s,v)$ a menor distância de $s$ a $v$, ou seja, o menor número de arcos em qualquer caminho de $s$ para $v$.

Para qualquer arco $(u,v)\in E$, temos que $\delta(s,v) \leq \delta(s, u) + 1$:

1. se $u$ é atingível, então $v$ atingível e o caminho mais curto para $v$ não pode ser superior ao caminho mais curto para $u$ mais o arco $(u,v)$;
2. se $u$ não é atingível, então o resultado é também válido (independentemente de $v$ ser atingível).

No final da BFS $\delta(u,v) =$ d[u], para todo o vértice $u$ de $v$.

Procura em profundidade primeiro / Depth First Search (DFS)

Numa DFS visitamos primeiro os arcos dos vértices mais recentemente visitados.

No final da procura temos uma floresta DF $G_\pi = (V, E_\pi)$, em que $E_\pi = \{(\pi[v], v) \ |\ v\in V \textrm{ e } \pi[v]\neq NIL \}$. Notar que a floresta DF é na prática constituída por várias árvores DF.

Aplicações

1. Encontrar um caminho entre 2 vértices específicos, $u$ e $v$, num grafo sem pesos ou com pesos (grafo pesado).
2. Determinar se um grafo é conexo ou não.
3. Determinar a ordenação topológica de um grafo.

Implementação

• color[v]: cor do vértice $v$:
  • branco: não visitado;
  • cinzento: já visitado mas pelo menos um dos vértices adjacentes não foi visitado ou a procura em pelo menos um dos vértices adjacentes não foi terminada;
  • preto: já visitado e a procura nos vértices adjacentes já está terminada.
• pi[v]: predecessor de $v$ na árvore BF;
• d[v]: tempo de início da visita de $v$ (o tempo começa em 1);
• f[v]: tempo de fim da visita de $v$.

Implementação:

static int time;

void dfs(Graph G)
{
  int u;
  for (u = 0; u < G->V; u++) {
    color[u] = WHITE;
    p[u] = -1;
  }
  time = 1;
  for (u = 0; u < G->V; u++)
    if(color[u] == WHITE)
      dfs_visit(G, u);
}

void dfs_visit(Graph G, int u)
{
  int v;
  color[u] = GRAY;d[u] = time;
  time++;
  for (v = 0; v < G->V; v++)
    if (G->adj[u][v] == 1) {
      if (color[v] == WHITE) {
        p[v] = u;
        dfs_visit(G, v);
      }
    }
  color[u] = BLACK;
  f[u] = time;
  time++;
}

Exercício: Implementar para grafos representados com listas de adjacências em vez de matriz de adjacências.

Exemplo

Neste exemplo vamos também classificar os arcos enquanto arcos de árvore (os que aparecem na floresta DFS no final), arcos para trás (que ligam a um antecessor durante a visita), arcos para a frente (que ligam a um descendente já visitado), e arcos de cruzamento (que ligam a um vértice já visitado, mas que não é nem antecessor nem descendente do vértice actual).

Floresta DFS:

Complexidade

O tempo de execução da DFS depende da representação utilizada para os grafos. No caso da matriz de adjacências temos $O(V^2)$:

• a inicialização corre em tempo $O(V)$;
• ocorrem no máximo $O(V)$ chamadas à função dfs_visit dentro da função dfs e cada nó só é visitado uma vez pela função dfs_visit (quando está branco), portanto temos $O(V)$ chamadas à função dfs_visit;
• cada linha da matriz é visitada 1 vez na função dfs_visit para cada vértice, portanto $O(V^2)$.

No caso das listas de adjacências temos $O(V + E)$:

• a inicialização corre em tempo $O(V)$;
• ocorrem no máximo $O(V)$ chamadas à função dfs_visit dentro da função dfs e cada nó só é visitado uma vez pela função dfs_visit (quando está branco), portanto temos $O(V)$ chamadas à função dfs_visit;
• a lista de adjacências de cada vértice é visitada 1 vez na função dfs_visit, portanto $O(E)$ no total.