Home RecentChanges

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:

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

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

Lesson24bfs0.png

Lesson24bfs1.png

Lesson24bfs2.png

Lesson24bfs3.png

Lesson24bfs4.png

Lesson24bfs5.png

Lesson24bfs6.png

Lesson24bfs7.png

Lesson24bfs8.png

Lesson24bfs9.png

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)$:

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

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

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).

Lesson24dfs0.png

Lesson24dfs1.png

Lesson24dfs2.png

Lesson24dfs3.png

Lesson24dfs4.png

Lesson24dfs5.png

Lesson24dfs6.png

Lesson24dfs7.png

Lesson24dfs8.png

Lesson24dfs9.png

Lesson24dfs10.png

Lesson24dfs11.png

Lesson24dfs12.png

Lesson24dfs13.png

Lesson24dfs14.png

Lesson24dfs15.png

Floresta DFS:

Lesson24dfs16.png

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)$:

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