Algoritmos em grafos

Algoritmos em Grafos¶

Ordem de crescimento assintótico (Big-Oh)¶

Ao longo deste capítulo, o custo de tempo e de espaço de cada algoritmo é indicado por meio da notação assintótica (em particular, a notação Big-Oh), escrita como $O(\cdot)$. O objetivo aqui é oferecer uma noção de como interpretá-la.

A notação $O(g(n))$ descreve a ordem de crescimento de uma função, isto é, como o custo de um algoritmo escala à medida que o tamanho da entrada cresce ($n \to \infty$). Quando dizemos que um algoritmo é $O(n^2)$, leia-se “cresce na ordem de $n^2$”: dobrar o tamanho da entrada tende a quadruplicar o custo. O foco recai sobre a tendência de crescimento, não sobre o valor exato do número de operações.

Um aspecto essencial é que constantes multiplicativas e termos de ordem inferior são desprezíveis (e, portanto, ignorados) quando a variável da função assume valores muito altos. Considere, por exemplo, uma função como $n^2/2 + n/2 - 1$: embora tenha coeficientes e termos extras, trata-se de um polinômio de grau 2 — sua curva tem o mesmo formato de $n^2$, uma parábola. Como o interesse está no comportamento quando $n$ é grande, constantes não alteram a natureza nem o formato da curva de crescimento. Isso permite comparar algoritmos de forma abstrata, independente de detalhes de hardware ou implementação.

A escolha de um algoritmo com complexidade eficiente é crucial. A diferença entre $O(n^2)$ e $O(n^3)$ pode parecer pequena à primeira vista, mas cresce drasticamente: para $n = 1000$, $n^2 = 10^6$ enquanto $n^3 = 10^9$ — mil vezes mais operações. Por isso, ao longo do texto, prestaremos atenção não apenas à corretude de cada algoritmo, mas também à sua classe de complexidade, que determina sua viabilidade em instâncias grandes.

Diferentemente de problemas cuja entrada é descrita por um único tamanho $n$, algoritmos em grafos dependem de duas variáveis que descrevem o tamanho da entrada:

• $n = |V|$, número de vértices

• $m = |E|$, número de arestas

Isso é fundamental para interpretar as complexidades deste capítulo. A quantidade de arestas $m$ varia de 0 (grafo sem arestas) até $O(n^2)$ (grafo completo), de modo que expressões como $O(n + m)$ e $O(n^2)$ representam realidades distintas. Por exemplo, a lista de adjacência ocupa $O(n + m)$ de espaço — eficiente para grafos esparsos —, enquanto a matriz de adjacências sempre ocupa $O(n^2)$, independentemente de $m$. Ler $O(n + m)$ exige ter ambas as variáveis em mente: se o grafo for denso ($m \approx n^2$), então $O(n + m) = O(n^2)$; se for esparso ($m \approx n$), então $O(n + m) = O(n)$.

A tabela abaixo resume as complexidades mais comuns nos algoritmos de grafos que aparecerão ao longo deste capítulo, interpretadas em termos de $n$ (vértices) e $m$ (arestas):

Observe como a mesma notação pode comportar-se de forma distinta conforme a densidade do grafo. Ao aproximarmos $m$ em função de $n$, a função efetivamente plotada fica explícita: no caso esparso ($m \approx n$), $O(n + m) \sim O(n)$; no caso denso ($m \approx n^2$), $O(n + m) \sim O(n^2)$. A figura abaixo deixa essas substituições visíveis nos rótulos de cada curva. O eixo horizontal representa o número de vértices $n$ — as arestas $m$ variam conforme o regime de densidade.

import matplotlib as mpl
import matplotlib.pyplot as plt
import numpy as np

mpl.rcParams['figure.dpi'] = 300

n = np.linspace(2, 20, 100)

m_esparso = n        # grafo esparso: m ≈ n
m_denso = n**2       # grafo denso: m ≈ n²

plt.figure(figsize=(5, 3.5))

plt.plot(n, n + m_esparso, "-", label=r"$O(n{+}m) \sim O(n)$ esparso ($m \approx n$)")
plt.plot(n, m_esparso * np.log2(n), "--", label=r"$O(m \log n) \sim O(n \log n)$ esparso ($m \approx n$)")
plt.plot(n, n + m_denso, ":", label=r"$O(n{+}m) \sim O(n^2)$ denso ($m \approx n^2$)")
plt.plot(n, m_denso * np.log2(n), "-.", label=r"$O(m \log n) \sim O(n^2 \log n)$ denso ($m \approx n^2$)")
plt.plot(n, n**3, "-", linewidth=3, label=r"$O(n^3)$")

plt.xlabel(r"Número de vértices ($n$)", fontsize=8)
plt.ylabel(r"Custo (operações)", fontsize=8)
plt.xticks(fontsize=7)
plt.yticks([])
plt.legend(fontsize=6, loc="upper left")
plt.grid(True)

plt.savefig("images/crescimento-grafos.png")
plt.show()

5.1 Representações de grafos¶

5.1.1 Introdução¶

$G = (V, E)$, $n = |V|$, $m = |E|$. Duas representações básicas:

Densidade $d = \frac{2m}{n(n-1)}$: $d \approx 1$ → denso (matriz); $d \approx 0$ → esparso (lista).

5.1.2 Matriz de Adjacências¶

M[u][v] vale 1 se existe a aresta $u \to v$, 0 caso contrário.

    0 1 2 3 4
  ┌───────────┐
0 │ 0 1 1 0 0 │
1 │ 0 0 1 1 0 │
2 │ 0 0 0 0 1 │
3 │ 0 0 0 0 1 │
4 │ 0 0 0 0 0 │
  └───────────┘

Implementação em C¶

#include <stdio.h>

#define MAXN 100

int main() {
    int n, m;

    // matriz de adjacência, inicializada com zeros
    int MA[MAXN][MAXN] = {0};

    // leitura: n vértices e m arestas
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        MA[u][v] = 1;           // digrafo: aresta u -> v
        // MA[v][u] = 1;       // não-direcionado: descomente esta linha
    }

    // impressão da matriz n x n
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++)
            printf("%d ", MA[u][v]);
        printf("\n");
    }

    return 0;
}

Implementação em C++¶

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // matriz n x n inicializada com 0
    vector<vector<int>> MA(n, vector<int>(n, 0));

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        MA[u][v] = 1;           // digrafo: aresta u -> v
        // MA[v][u] = 1;       // não-direcionado: descomente esta linha
    }

    // impressão da matriz
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            cout << MA[u][v] << " ";
        }
        cout << "\n";
    }

    return 0;
}

vector é um array dinâmico: cresce automaticamente, push_back anexa ao final em $O(1)$ amortizado.

Complexidade¶

5.1.3 Lista de Adjacência¶

LA[u] guarda apenas os vizinhos de $u$ — espaço proporcional a $m$, não a $n^2$.

LA[0] -> 1 -> 2
LA[1] -> 2 -> 3
LA[2] -> 4
LA[3] -> 4
LA[4] -> (vazia)

Implementação em C (lista ligada)¶

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000

typedef struct no {
    int v;               // vértice de destino
    struct no* prox;     // próximo nó da lista
} no;

// LA[u] aponta para o primeiro vizinho de u (NULL se não houver)
no* LA[MAXN];

// insere v na lista de adjacência de u (inserção no início: O(1))
void insere(int u, int v) {
    no* novo = (no*) malloc(sizeof(no));
    novo->v = v;
    novo->prox = LA[u];
    LA[u] = novo;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        insere(u, v);            // digrafo: aresta u -> v
        // insere(v, u);        // não-direcionado: descomente esta linha
    }

    // impressão
    for (int u = 0; u < n; u++) {
        printf("%d:", u);
        for (no* p = LA[u]; p != NULL; p = p->prox)
            printf(" %d", p->v);
        printf("\n");
    }

    // liberação de memória
    for (int u = 0; u < n; u++) {
        no* p = LA[u];
        while (p != NULL) {
            no* tmp = p;
            p = p->prox;
            free(tmp);
        }
    }

    return 0;
}

Inserção no início é $O(1)$ mas inverte a ordem dos vizinhos.

Implementação em C++ (vector)¶

#include <iostream>
#include <vector>
using namespace std;

typedef vector<int> vi;    // apelido: "lista de vizinhos"

int main() {
    int n, m;
    cin >> n >> m;

    // vetor de n listas de adjacência
    vi* LA = new vi[n];

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        LA[u].push_back(v);     // digrafo: aresta u -> v
        // LA[v].push_back(u); // não-direcionado: descomente esta linha
    }

    // impressão (range-based for — C++11)
    for (int u = 0; u < n; u++) {
        cout << u << ":";
        for (int v : LA[u])
            cout << " " << v;
        cout << "\n";
    }

    delete[] LA;
    return 0;
}

Consultar se uma aresta existe¶

Não há acesso direto — é preciso percorrer ($O(\deg(u))$):

// C
int existe_aresta(no** LA, int u, int v) {
    for (no* p = LA[u]; p != NULL; p = p->prox) {
        if (p->v == v) return 1;
    }
    return 0;
}

// C++
bool existe_aresta(vi* LA, int u, int v) {
    for (int vizinho : LA[u]) {
        if (vizinho == v) return true;
    }
    return false;
}

Complexidade¶

5.1.4 Extensão para grafos ponderados¶

Em C (struct com peso)¶

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000

typedef struct aresta {
    int v;               // vértice de destino
    int w;               // peso da aresta
    struct aresta* prox;
} aresta;

aresta* LA[MAXN];

void insere(int u, int v, int w) {
    aresta* novo = (aresta*) malloc(sizeof(aresta));
    novo->v = v;
    novo->w = w;
    novo->prox = LA[u];
    LA[u] = novo;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        insere(u, v, w);          // digrafo ponderado: u -> v com peso w
        // insere(v, u, w);      // não-direcionado: descomente
    }

    for (int u = 0; u < n; u++) {
        printf("%d:", u);
        for (aresta* p = LA[u]; p != NULL; p = p->prox)
            printf(" (%d,%d)", p->v, p->w);
        printf("\n");
    }

    // liberação (mesma lógica da versão sem peso)
    for (int u = 0; u < n; u++) {
        aresta* p = LA[u];
        while (p != NULL) {
            aresta* tmp = p;
            p = p->prox;
            free(tmp);
        }
    }

    return 0;
}

Em C++ (pair)¶

pair<int,int> (biblioteca <utility>) agrupa (destino, peso) sem definir struct.

#include <iostream>
#include <vector>
#include <utility>   // pair, make_pair
using namespace std;

typedef pair<int,int> ii;       // (vértice destino, peso)
typedef vector<ii> vii;         // lista de adjacência ponderada

int main() {
    int n, m;
    cin >> n >> m;

    vii* LA = new vii[n];

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        LA[u].push_back(make_pair(v, w));    // aresta u -> v com peso w
        // LA[v].push_back(make_pair(u, w)); // não-direcionado: descomente
    }

    // impressão: a.first = vértice, a.second = peso
    for (int u = 0; u < n; u++) {
        cout << u << ":";
        for (ii a : LA[u])
            cout << " (" << a.first << "," << a.second << ")";
        cout << "\n";
    }

    delete[] LA;
    return 0;
}

Para matriz ponderada, troque 1/0 pelo peso e use um sentinela (ex.: INT_MAX) para ausência de aresta.

5.1.5 Variantes avançadas¶

set/map (C++)¶

A lista com vector consulta arestas em $O(\deg(u))$. Substituindo o container, melhora-se a consulta:

#include <iostream>
#include <set>
using namespace std;

typedef set<int> si;    // conjunto ordenado de vizinhos

int main() {
    int n, m;
    cin >> n >> m;

    // cada LA[u] é um set<int> (árvore balanceada)
    si* LA = new si[n];

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        LA[u].insert(v);       // inserção O(log deg(u))
        // LA[v].insert(u);   // não-direcionado: descomente
    }

    // consulta: existe aresta u -> v?  O(log deg(u))
    // LA[u].count(v) retorna 1 se v está no conjunto, 0 caso contrário

    // impressão (set percorre em ordem crescente automaticamente)
    for (int u = 0; u < n; u++) {
        cout << u << ":";
        for (int v : LA[u])
            cout << " " << v;
        cout << "\n";
    }

    delete[] LA;
    return 0;
}

Para grafos ponderados: map<int,int> (árvore rubro-negra) mapeia vizinho $\to$ peso; unordered_map (hash table) oferece $O(1)$ médio.

typedef map<int,int> mii;    // vizinho -> peso
// LA[u][v] = w;      // define o peso da aresta u -> v
// LA[u].count(v);    // verifica se a aresta existe

Compressed Sparse Row (CSR)¶

Formato para processamento de grafos muito usado em álgebra linear esparsa (exemplo: processamento de grafos em GPU). Dois arrays contíguos:

Número de vizinhos de $u$: row_ptr[u+1] - row_ptr[u].

for (i = row_ptr[u]; i < row_ptr[u+1]; i++) {
    v = col_idx[i];
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // leitura das arestas
    vector<int> origem(m), destino(m);
    for (int i = 0; i < m; i++)
        cin >> origem[i] >> destino[i];

    // 1. contar grau de cada vértice
    vector<int> row_ptr(n + 1, 0);
    for (int i = 0; i < m; i++)
        row_ptr[origem[i] + 1]++;

    // 2. soma prefixa: row_ptr[u] = início dos vizinhos de u em col_idx
    for (int u = 0; u < n; u++)
        row_ptr[u + 1] += row_ptr[u];

    // 3. preencher col_idx (preserva a ordem de leitura das arestas)
    vector<int> col_idx(m);
    vector<int> pos = row_ptr;    // posição de escrita atual por vértice
    for (int i = 0; i < m; i++) {
        int u = origem[i];
        col_idx[pos[u]] = destino[i];
        pos[u]++;
    }

    // impressão
    for (int u = 0; u < n; u++) {
        cout << u << ":";
        for (int i = row_ptr[u]; i < row_ptr[u + 1]; i++)
            cout << " " << col_idx[i];
        cout << "\n";
    }

    return 0;
}

Para grafos ponderados, adicione um array values[] paralelo a col_idx[].

5.1.6 Entrada de exemplo e compilação¶

Salve como input.txt:

5 6
0 1
0 2
1 2
1 3
2 4
3 4

# C
gcc matriz-adjacencias.c -o matriz-c
gcc lista-adjacencia.c -o lista-c

# C++
g++ -std=c++17 matriz-adjacencias.cpp -o matriz-cpp
g++ -std=c++17 lista-adjacencia.cpp -o lista-cpp
g++ -std=c++17 lista-set.cpp -o lista-set
g++ -std=c++17 csr.cpp -o csr

# Executar (todos leem o mesmo input.txt)
./matriz-c < input.txt
./lista-c   < input.txt
./matriz-cpp < input.txt
./lista-cpp  < input.txt
./lista-set  < input.txt
./csr        < input.txt

Saída esperada da matriz:

0 1 1 0 0
0 0 1 1 0
0 0 0 0 1
0 0 0 0 1
0 0 0 0 0

Saída esperada da lista (C++, com push_back — preserva ordem de inserção):

0: 1 2
1: 2 3
2: 4
3: 4
4:

Em C (lista ligada com inserção no início), a ordem dos vizinhos aparece invertida.

Para a versão ponderada, use uma entrada com três valores por linha:

5 6
0 1 10
0 2 5
1 2 2
1 3 7
2 4 3
3 4 1

5.2 Fecho transitivo (Algoritmo de Warshall)¶

O fecho transitivo de um grafo direcionado $G = (V, E)$ é o grafo $G^* = (V, E^*)$ onde $E^*$ contém todo par $(u, v)$ tal que existe um caminho de $u$ a $v$ em $G$. Frequentemente, nos referimos ao algoritmo que computa essa propriedade através do nome de seu autor (Algoritmo de Warshall). A ideia central é estender progressivamente o conjunto de vértices intermediários permitidos: a cada passo $k$, verificamos se incluir $k$ como intermediário cria novos caminhos entre pares de vértices. O algoritmo de Warshall é fundamental por (1) determinar a alcançabilidade entre todos os pares de vértices; (2) revelar a estrutura de conectividade do grafo; (3) servir como base para o algoritmo de Floyd-Warshall, que estende a mesma estrutura para caminhos mínimos ponderados. De fato, como exemplo, o fecho transitivo é geralmente usado para verificar se um grafo é fortemente conectado e para identificar componentes fortemente conectados.

O pseudocódigo é indicado abaixo, mas algumas informações são importantes:

• A entrada é um grafo direcionado $G$ com matriz de adjacências $G.M$ de dimensão $n \times n$

• O algoritmo computa uma sequência de matrizes $W_0, W_1, \ldots, W_n$, onde $W_k[u][v] = 1$ se, e somente se, existe caminho de $u$ a $v$ usando apenas vértices intermediários em $\{1, \ldots, k\}$

• Caso base ($W_0 = G.M$): apenas arestas diretas são consideradas: $W_0[u][v] = 1$ sse existe a aresta $(u, v)$. Isto é, inicialmente a própria matriz de adjacências.

• Recorrência: $W_k[u][v] = W_{k-1}[u][v] \lor (W_{k-1}[u][k] \land W_{k-1}[k][v])$ — ou já existe caminho sem $k$, ou passa por $k$

• Resultado final: $W_n$ é o fecho transitivo de $G$

WARSHALL(G)
// argumentos:
// G: grafo direcionado com vértices V e matriz de adjacências G.M (n x n)

W_0 = G.M                       // caso base: apenas arestas diretas
for k = 1 to n
   W_k = nova matriz (n x n)    // nova matriz alocada para este intermediário
   for u = 1 to n
      for v = 1 to n
         W_k[u][v] = W_{k-1}[u][v] OR (W_{k-1}[u][k] AND W_{k-1}[k][v])
return W_n

Complexidade de tempo: Observe que, sendo $n$ a quantidade de vértices do grafo, temos três laços aninhados cada um executando uma quantidade fixa de iterações ($1 \cdots n$). Assim, temos um algoritmo que totaliza uma ordem de $O(n^3)$ operações.

Complexidade de espaço: O algoritmo aloca uma nova matriz W_i de tamanho $(n \times n)$ a cada iteração de vértices intermediários $k$, totalizando $n \times O(n^2) = O(n^3)$ na ordem de espaço gasto. É possível otimizar o custo de espaço de $O(n^3)$ para $O(n^2)$ atualizando a mesma matriz in-place a cada iteração $k$. Isso é seguro porque a $k$-ésima linha e coluna não se alteram: como W_{k-1}[k][k] = 1, temos W_k[u][k] = W_{k-1}[u][k] OR (W_{k-1}[u][k] AND 1) = W_{k-1}[u][k], e analogamente W_k[k][v] = W_{k-1}[k][v]. Logo, os valores lidos durante a atualização in-place são exatamente os mesmos que seriam lidos da matriz anterior.

5.3 Caminhamento em largura (Breadth-first search - BFS)¶

Um caminhamento (ou busca) em largura é um procedimento cujo objetivo é visitar (encontrar) cada vértice de um grafo e, naturalmente, seguindo as arestas. Frequentemente, nos referimos a essa busca através do nome em inglês e sua sigla (Breadth-First Search - BFS). Busca em largura significa que os vizinhos de um vértice são todos visitados antes que possamos cogitar visitar vizinhos dos vizinhos (remete a uma ideia de fila FIFO). A BFS é um algoritmo tão fundamental que é utilizada para (1) extrair propriedades estruturais de um grafo; (2) consultar atributos de vértices e arestas de forma ordenada e eficiente; (3) como subrotina de outras tarefas em grafos. De fato, como exemplo, a BFS é geralmente é usada para encontrar distâncias mínimas de um vértice a todos os outros em relação ao número de arestas.

O pseudocódigo é indicado abaixo, mas algumas informações são importantes:

• A entrada é um grafo não-ponderado e um vértice de partida ($s$)

• O algoritmo marca três informações para cada vértice: sua cor, sua distância partindo de $s$, qual vértice (pai) o descobriu

• Cores ($u.color$): [WHITE] indica que o vértice ainda não foi descoberto; [GRAY] indica que o vértice foi descoberto porém não foi visitado; [BLACK] vértice descoberto e visitado

• Distância ($u.d$): indica quantas arestas existem partindo de $s$ com destino a $u$, considerando a busca em largura

• Predecessor/pai ($u.\pi$): marca, para cada vértice, quem foi o vértice que o descobriu -- naturalmente ninguém descobre $s$

BFS(G, s)
// argumentos:
// G: grafo com vértices V e listas de adjacências Adjlist
// s: vértice fonte que representa o ponto de partida da busca 

for each vertex u in G.V except s
   u.pi = NIL
   u.d = infinity
   u.color = WHITE
s.color = GRAY
s.d = 0
s.pi = NIL
Q = queue containing s
while Q is not empty
   u = dequeue(Q) // próximo da fila FIFO
   for each v in G.AdjList[u]
      if v.color == WHITE
         v.color = GRAY
         v.pi = u
         v.d = u.d + 1
         enqueue(Q, v)
      u.color = BLACK    // BLACK: totalmente explorado

5.3.1 Grafos de exemplo para exercitar BFS¶

Exemplos:

import matplotlib as mpl
import matplotlib.pyplot as plt
import networkx as nx

mpl.rcParams['figure.dpi'] = 300

fig, axes = plt.subplots(1, 3, figsize=(9, 3))

# Grafo 1: não direcionado, 6 vértices, conexo
G1 = nx.Graph()
G1.add_edges_from([(0,1),(0,2),(1,3),(2,3),(3,4),(2,5),(4,5)])
pos1 = {0:(0,1), 1:(1,2), 2:(1,0), 3:(2,1), 4:(3,1.5), 5:(3,0.5)}
nx.draw(G1, pos1, ax=axes[0], with_labels=True, node_color='#4C9F70',
        node_size=350, font_size=9, font_color='white', edge_color='#333',
        width=1.5)
axes[0].set_title("")

# Grafo 2: direcionado, 5 vértices, com antiparalelas
G2 = nx.DiGraph()
G2.add_edges_from([(0,1),(1,0),(0,2),(1,3),(2,3),(3,4),(4,1),(2,4)])
pos2 = {0:(0,1), 1:(1,2), 2:(1,0), 3:(2,1), 4:(3,1)}
nx.draw(G2, pos2, ax=axes[1], with_labels=True, node_color='#4C9F70',
        node_size=350, font_size=9, font_color='white', edge_color='#333',
        width=1.5, arrowsize=12, connectionstyle='arc3,rad=0.15')
axes[1].set_title("")

# Grafo 3: não direcionado, 7 vértices, com "cul-de-sac"
G3 = nx.Graph()
G3.add_edges_from([(0,1),(0,3),(1,2),(1,4),(3,5),(5,6),(4,6)])
pos3 = {0:(0,1), 1:(1,2), 2:(2,2.5), 3:(1,0), 4:(2,1.5), 5:(2,0), 6:(3,0.5)}
nx.draw(G3, pos3, ax=axes[2], with_labels=True, node_color='#4C9F70',
        node_size=350, font_size=9, font_color='white', edge_color='#333',
        width=1.5)
axes[2].set_title("")

plt.tight_layout()
plt.savefig("images/exemplos-bfs.png")
plt.show()

5.4 Caminhamento em profundidade (Depth-first search - DFS)¶

Um caminhamento (ou busca) em profundidade é um procedimento cujo objetivo é, assim como a busca em largura, visitar (encontrar) cada vértice de um grafo seguindo as arestas. Frequentemente, nos referimos a essa busca através do nome em inglês e sua sigla (Depth-First Search - DFS). Busca em profundidade significa que, a partir de um vértice, exploramos o mais profundamente possível cada ramo antes de retroceder (backtrack) e visitar outros vizinhos (remete a uma ideia de pilha LIFO, naturalmente implementada via recursão). A DFS é um algoritmo tão fundamental que é utilizada para (1) classificar arestas de um grafo direcionado; (2) realizar ordenação topológica em DAGs; (3) encontrar componentes fortemente conectados; (4) detectar ciclos. De fato, como exemplo, a DFS é geralmente usada para determinar a estrutura de ancestralidade entre vértices por meio dos tempos de descoberta e término.

O pseudocódigo é indicado abaixo, mas algumas informações são importantes:

• A entrada é um grafo (direcionado ou não) — diferentemente da BFS, não há um vértice de partida fixo; o algoritmo percorre todos os vértices, iniciando uma busca sempre que encontra um vértice ainda não descoberto

• O algoritmo marca quatro informações para cada vértice: sua cor, seu tempo de descoberta, seu tempo de término, qual vértice (pai) o descobriu

• Cores ($u.color$): [WHITE] indica que o vértice ainda não foi descoberto; [GRAY] indica que o vértice foi descoberto porém ainda está sendo explorado (há descendentes em processamento); [BLACK] vértice descoberto e totalmente explorado

• Tempo de descoberta ($u.d$): marca o instante em que o vértice foi descoberto (quando se torna GRAY)

• Tempo de término ($u.f$): marca o instante em que o vértice terminou de ser explorado (quando se torna BLACK)

• Predecessor/pai ($u.\pi$): marca, para cada vértice, quem foi o vértice que o descobriu -- naturalmente ninguém descobre a raiz de cada árvore da floresta de predecessores

DFS(G)
 // argumentos:
 // G: grafo com vértices V e listas de adjacências Adjlist

 for each vertex u in G.V
    u.color = WHITE
    u.pi = NIL
 for each vertex u in G.V
    if u.color == WHITE
       DFS-VISIT(G, u)

time = 0    // variável global para marcar os tempos dos vértices
DFS-VISIT(G, u)
 time = time + 1
 u.d = time
 u.color = GRAY
 for each v in G.AdjList[u]
    if v.color == WHITE
       v.pi = u
       DFS-VISIT(G, v)
 u.color = BLACK
 time = time + 1
 u.f = time

• O intervalo $[u.d, u.f ]$ está totalmente contido dentro do intervalo $[v.d, v.f]$ sse $u$ é descendente de $v$ em alguma a´rvore na floresta de predecessores do DFS (ou vice versa)
  

• O intervalo $[u.d, u.f]$ é totalmente disjunto de $[v.d, v.f]$ sse os dois vértices pertencem a árvores diferentes na floresta de predecessores do DFS.
  

• Não é possível que intervalos tenham sobreposição mas que um não esteja totalmente contido dentro do outro: se isso pudesse acontecer, teríamos que o vértice ancestral seria terminado antes do seu descendente, o que contraria a definição de caminhamento em profundidade já que vértices ancestrais só terminam quando todos os seus descendentes tenham terminado.

5.4.1 Grafos de exemplo para exercitar DFS¶

Exemplos:

import matplotlib as mpl
import matplotlib.pyplot as plt
import networkx as nx

mpl.rcParams['figure.dpi'] = 300

fig, axes = plt.subplots(1, 3, figsize=(10, 3.5))

# Grafo 1: direcionado, 7 vértices — exercita tree, back, forward e cross edges
G1 = nx.DiGraph()
G1.add_edges_from([(0,1),(1,2),(2,1),(2,3),(3,4),(4,5),(5,1),(1,3),(0,2),(6,2),(6,5),(3,0)])
pos1 = nx.spring_layout(G1, seed=42)
nx.draw(G1, pos1, ax=axes[0], with_labels=True, node_color='#C75B4A',
        node_size=350, font_size=9, font_color='white', edge_color='#333',
        width=1.5, arrowsize=12, connectionstyle='arc3,rad=0.15')
axes[0].set_title("")

# Grafo 2: direcionado, 6 vértices, DAG com múltiplos caminhos
G2 = nx.DiGraph()
G2.add_edges_from([(0,1),(0,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,5),(1,4),(0,3)])
pos2 = nx.spring_layout(G2, seed=42)
nx.draw(G2, pos2, ax=axes[1], with_labels=True, node_color='#C75B4A',
        node_size=350, font_size=9, font_color='white', edge_color='#333',
        width=1.5, arrowsize=12, connectionstyle='arc3,rad=0.15')
axes[1].set_title("")

# Grafo 3: não direcionado, 7 vértices, com articulação e ciclo
G3 = nx.Graph()
G3.add_edges_from([(0,1),(0,2),(1,2),(1,3),(3,4),(4,5),(4,6),(5,6)])
pos3 = nx.spring_layout(G3, seed=42)
nx.draw(G3, pos3, ax=axes[2], with_labels=True, node_color='#C75B4A',
        node_size=350, font_size=9, font_color='white', edge_color='#333',
        width=1.5)
axes[2].set_title("")

plt.tight_layout()
plt.savefig("images/exemplos-dfs.png")
plt.show()

5.4.2 Classificação de arestas em DFS¶

Se considerarmos o caso mais geral com grafos direcionados, podemos classificar as arestas de um grafo em quatro categorias:

1. Arestas da árvore (tree edges) são aquelas que aparecem na floresta de predecessores – aquelas que são selecionadas para visitar novos vértices;
   

2. Arestas de volta (back edges) são aquelas que vão de um descendente para algum de seus ancestrais na árvore DFS;
   

3. Arestas avançadas (forward edges) são aquelas que vão de um vértice até algum de seus descendentes na árvore DFS;
   

4. Arestas de cruzamento (cross edges) são as outras arestas: pode acontecer entre vértices de diferentes árvores da floresta ou mesmo entre vértices da mesma árvore que não compartilham relação ancestral/descendente (irmãos, por exemplo);

Toda vez que visitamos um novo vértice v no DFS, digamos através da aresta $(u, v)$, temos alguma informação sobre qual tipo de aresta ela será. Se a cor de v for $WHITE$, então a aresta $(u, v)$ é uma aresta da árvore (tree edge). Se a cor do vértice $v$ for $GRAY$ , então a aresta $(u, v)$ é de volta (back). Se a cor de $v$ for $BLACK$, então a aresta pode ser avançada (forward) ou de cruzamento (cross). Podemos tirar essa última dúvida se a aresta é avançada ou de cruzamento ao observar os tempos de cada aresta: se além de ser $BLACK$, o intervalo de u for disjunto do intervalo de v então temos uma aresta de cruzamento sem relação ancestral/descendente; caso contrário, se os intervalos estiverem contido um dentro do outro, temos uma aresta avançada, já que a sobreposição indica ancestralidade (pela parentização).

5.4.3 Detecção de articulações e pontes¶

O algoritmo de Tarjan estende a DFS com dois atributos adicionais além dos já conhecidos ($u.color$, $u.d$, $u.\pi$):

• Tempo de descoberta ($u.d$): marca o instante em que $u$ foi descoberto, como no DFS padrão

• Menor alcançável ($u.low$): o menor tempo de descoberta alcançável a partir da subárvore DFS enraizada em $u$, descendo por arestas de árvore e subindo por no máximo uma aresta de volta. Inicialmente $u.low = u.d$ e, durante o caminhamento, $u.low$ é atualizado ao considerar: (1) arestas de árvore — $u.low = \min(u.low, v.low)$ após visitar o filho $v$; (2) arestas de volta — $u.low = \min(u.low, v.d)$ quando $v$ é um ancestral.

Em grafos não direcionados, toda aresta de volta define um ciclo, de modo que $u.low$ rastreia, em essência, até onde os ciclos da subárvore conseguem subir em direção à raiz. Se $u.low < u.d$, existe um ciclo que conecta a subárvore de $u$ a algum ancestral acima de $u$, funcionando como caminho alternativo de conectividade. Se $u.low = u.d$, nenhum ciclo escapa acima de $u$ e a subárvore pende isolada — justamente o que caracteriza articulações e pontes:

• Se $v.low \geq u.d$, a subárvore de $v$ não alcança ancestral de $u$ $\Rightarrow$ $u$ é articulação

• Se $v.low > u.d$, a subárvore de $v$ tampouco alcança $u$ $\Rightarrow$ $(u,v)$ é ponte

• A raiz da DFS é articulação sse possui mais de um filho na floresta de predecessores

time = 0        // variável global para marcar os tempos dos vértices

TARJAN-PONTES-ARTICULACOES(G)
 // argumentos:
 // G: grafo com vértices V e listas de adjacências Adjlist
 // ART: conjunto global de articulações (vértices de corte)
 // PONTES: conjunto global de pontes (arestas cuja remoção desconecta o grafo)

 ART = {}        // conjunto global de articulações
 PONTES = {}     // conjunto global de pontes
 for each vertex u in G.V
    u.color = WHITE
    u.pi = NIL
 for each vertex u in G.V
    if u.color == WHITE
        nchildren = DFS-TARJAN(G, u)
        if nchildren > 1
            ART = ART union {u}     // raiz com mais de um filho é articulação
 return ART, PONTES

DFS-TARJAN(G, u)
 u.color = GRAY
 nchildren = 0
 time = time + 1
 u.d = time
 u.low = time
 for each v in G.AdjList[u]
    if v.color == WHITE     // (u,v) é aresta de árvore
        v.pi = u
        nchildren = nchildren + 1
        DFS-TARJAN(G, v)
        if u.pi != NIL and v.low >= u.d
            ART = ART union {u}            // u (não-raiz) é articulação
        if v.low > u.d
            PONTES = PONTES union {(u,v)}  // (u,v) é ponte
        u.low = min(u.low, v.low)
    else if v != u.pi
        u.low = min(u.low, v.d)
 u.color = BLACK
 return nchildren

5.4.4 Ordenação topológica¶

A ideia é que vértices que terminam primeiro devem ser posicionados depois de todos os seus ancestrais na ordenação topológica.

Topological-Sort(G)
 // G: Grafo direcionado acíclico com vértices V e lista de adjacência AdjList

 chame DFS(G), registrando os tempos de término para cada vértice
 à medida que cada vértice termina, insira-o no início de uma lista ligada
 retorne a lista ligada de vértices

5.4.5 Encontrando componentes fortemente conectados¶

A ideia aqui é que ao executar o DFS em $G^T$ , sempre visitamos primeiro aqueles vértices de maior tempo de término em $G$, ou seja, aqueles vértices que não possuem aresta para outros vértices posicionados antes na ordem topológica. Dessa forma, toda vez que um vértice branco é encontrado, podemos ter certeza de que ele pertence à componente atual e toda vez que encontramos vértices já terminados, sabemos se tratar de vértices cuja componente já determinamos em uma visita anterior.

STRONGLY-CONNECTED-COMPONENTS(G)
// G: Grafo direcionado com vértices V e lista de adjacência AdjList

1. chame DFS(G) para determinar os tempos de término de cada vértice do grafo
2. construa G^T, que representa G com suas arestas invertidas
3. chame DFS(G^T), visitando primeiro os vértices com maior tempo de término (passo 1)
4. cada árvore da floresta visitada pelo último caminhamento representa um componente fortemente conectado do grafo original

5.5 Árvores geradoras de custo mínimo¶

5.5.1 Algoritmo de Prim¶

Fazemos $|V|$ operações de EXTRACT-MIN, uma para cada vértice, totalizando $O(V \;log \;V )$. Além disso, no pior caso, as chaves dos vértices são atualizadas $O(E)$ vezes, já que fazemos isso para as listas de adjacências do grafo. Como cada operação DECREASE-KEY custa $O(log \;V )$, temos o total de $O(V \;log \;V + E \;log \;V ) = O(E \;log \;V )$. Usando Fibonacci heaps, podemos melhorar esse custo assintótico para $O(E + V \;log \;V )$: isso acontece porque nessa estrutura, o custo amortizado de $V$ operações EXTRACT-MIN continua sendo $O(log \;V )$, mas o custo amortizado de $O(E)$ operações DECREASE-KEY fica reduzido para $O(1)$ (ao invés de $O(log \;V )$ no heap tradicional).

MST-PRIM(G, w, r)
// argumentos:
// G: grafo com vértices V e arestas E
// w: função de peso das arestas
// r: vértice de partida

for each u in V
   u.pi = NIL
   u.key = infinity
r.key = 0
Q = PRIORITY-QUEUE(G.V) // fila de prioridades chaveada por u.key
while Q != empty
   u = EXTRACT-MIN(Q)
   for each vertex v in G.AdjList[u]
      if v in Q and w(u, v) < v.key
         v.key = w(u, v)
         v.pi = u
         DECREASE-KEY(Q, v, v.key)

5.5.2 Algoritmo de Kruskal¶

O algoritmo faz $V$ operações MAKE-SET e $E$ operações FIND-SET/UNION. O custo dessas operações usando uma estrutura de dados para union/find é uma função que cresce bem lentamente e é limitada superiormente por $O(log \;V )$. Portanto, o custo total do algoritmo é $O((V + E) log \;V )$. Mas como em um grafo conectado temos $E ≥ V − 1$, totalizando $O(E \;log \;V )$.

MST-KRUSKAL(G(V, E), w)
// argumentos:
// G(V, E): grafo com vértices V e arestas E
// w: função de peso das arestas

A = {}
for each u in V
   MAKE-SET(u)
E' = SORT-BY-WEIGHT-NONDECREASING(E, w) // ordena arestas por w em ordem não-decrescente
for each (u, v) in E' // em ordem
   if FIND-SET(u) != FIND-SET(v)
      A = A union {(u, v)}
      UNION(u, v)

5.6 Propriedades de caminhos mínimos¶

• Desigualdade triangular:
  $δ(s, v) ≤ δ(s, u) + w(u, v)$
  O menor caminho entre $s$ e $v$ não pode ser maior do que o menor caminho entre $s$ e $u$ mais o custo da aresta $(u, v)$, senão teríamos um caminho de custo menor para $v$ (contradição).
  

• Propriedade do limite superior:
  É sempre verdade que a estimativa de menor caminho para $v$, $v.d$, é sempre maior do que o menor caminho real até $v$:
  $δ(s, v) ≤ v.d$.
  

• Propriedade do não-caminho:
  Se não existir caminho entre dois vértices (grafo orientado), temos que:
  $δ(s, v) = ∞$.
  

• Propriedade da convergência:
  Seja um caminho $s ⇝ u → v$, se relaxamos a aresta $(u, v)$ depois de já termos encontrado o caminho mínimo para $u$ (isto é, $u.d = δ(s, u)$), então:
  $v.d = δ(s, v)$
  E o mais importante, essa estimativa ótima nunca mais será alterada.
  

• Propriedade do relaxamento de um caminho:
  Seja um caminho mínimo $s ⇝ v$, se relaxamos as arestas na ordem desse caminho, então a estimativa do menor caminho para $v$ se tornará o menor caminho real:
  $v.d = δ(s, v)$.
  

• Propriedade do predecessor:
  Ao computar todas as estimativas para o menor caminho, $v.d = δ(s, v)$, teremos uma árvore de caminhos mínimos cuja raiz é $s$.

5.7 Caminhos mínimos a partir de uma única fonte¶

5.7.1 Algoritmo de Bellman-Ford¶

RELAX(u, v, w)
// argumentos:
// u: vértice de origem
// v: vértice de destino
// w: função de peso das arestas

if v.d > u.d + w(u, v)
   v.d = u.d + w(u, v)
   v.pi = u

BELLMAN-FORD(G(V, E), w, s)
// argumentos:
// G(V, E): grafo com vértices V e arestas E
// w: função de peso das arestas
// s: vértice fonte

for each u in V
   u.pi = NIL
   u.d = infinity
s.d = 0

for i = 1 to |V| - 1
   for each (u, v) in E
      RELAX(u, v, w)

for each (u, v) in E
   if v.d > u.d + w(u, v)
      return false // existe ciclo negativo
return true

5.7.2 Algoritmo de Dijkstra¶

Este algoritmo utiliza uma escolha gulosa de sempre escolher para alcançar em seguida o vértice não alcançado que tenha a menor estimativa de distância até o momento. A inteligência do algoritmo vem do fato de que ao se alcançar um novo vértice, temos a oportunidade de melhorar a estimativa de distância de todos aqueles vértices não alcançados e que sejam adjacentes ao novo vértice.

O algoritmo faz $|V|$ operações EXTRACT-MIN e faz $O(|E|)$ operações DECREASE-KEY (que acontece quando relaxamos uma aresta e diminuímos a prioridade de um vértice). Essas duas operações podem ser implementadas com complexidade $O(log |V |)$ em um heap binário mínimo, totalizando $O((V + E) log \;V )$, ou $O(E \;log \;V )$ se todos os vértices forem alcançáveis (grafo conectado).

É possível obter um custo assintótico melhor se usarmos heaps Fibonacci, que oferecem um custo amortizado de $O(log \;V )$ por EXTRACT-MIN (o mesmo de antes), mas melhora o custo amortizado de DECREASE-KEY para $O(1)$, totalizando $O(V log \;V + E)$.

DIJKSTRA(G, w, s)
// argumentos:
// G: grafo com vértices V e arestas E
// w: função de peso das arestas
// s: vértice fonte

for each u in V
   u.pi = NIL
   u.d = infinity
s.d = 0
S = empty
Q = PRIORITY-QUEUE(G.V) // fila de prioridades chaveada por u.d
while Q != empty
   u = EXTRACT-MIN(Q)
   S = S union {u}
   for each vertex v in G.AdjList[u]
      if v.d > u.d + w(u, v)
         v.d = u.d + w(u, v)
         v.pi = u
         DECREASE-KEY(Q, v, v.d)

5.7.3 Caminhos mínimos em DAGs¶

Em grafos acíclicos direcionados (DAG), não temos ciclos por definição. Isso facilita nossa tarefa de obter caminhos mínimos pois podemos estabelecer qual serão as ordens dos caminhos mínimos. Sabendo disso, podemos relaxar as arestas em uma ordem específica e pela propriedade do relaxamento de um caminho, estamos garantidos que teremos a estimativa ótima para cada vértice. A ordem assim mencionada é diretamente obtida a partir de uma ordenação topológica do grafo de entrada. Observe que assim conseguimos obter os caminhos mínimos a partir de uma fonte em tempo linear $Θ(V + E)$.

DAG-SHORTEST-PATHS(G(V, E), w, s)
// argumentos:
// G(V, E): grafo direcionado acíclico com vértices V e arestas E
// w: função de peso das arestas
// s: vértice fonte

for each u in V
   u.pi = NIL
   u.d = infinity
s.d = 0

V' = TOPOLOGICAL-SORT(G)

for each u in V' // em ordem topológica
   for each v in G.AdjList[u]
      RELAX(u, v, w)

5.8 Caminhos mínimos entre todos os pares de vértices¶

Vamos assumir que os pesos das arestas estão organizados em uma matriz quadrada $w_{ij}$ e que uma matriz de predecessores $Π_{ij}$ armazena os caminhos mínimos entre cada par de vértices. Veremos que essa formulação nos ajudará a construir algoritmos para o caso em que os grafos são densos. A subestrutura de um caminho mínimo nos permite caracterizar uma equação para custos ótimos de subproblemas e também um algoritmo de programação dinâmica. Seja $l_{ij}$ o custo de um caminho mínimo entre o vértice $i$ e $j$. Sabemos que esse caminho pode ter, no máximo, $n − 1$ arestas onde $n = |V|$. Por isso, podemos caracterizar qualquer caminho mínimo em subcaminhos que usam uma quantidade de arestas. Seja $l^{(m)} _{i j}$ o custo do caminho mínimo entre $i$ e $j$ que usa, no máximo, $m$ arestas:

Com essa equação, conseguimos dois algoritmos para o problema.

O primeiro constrói $l^{(0)} _{ij} ⇝ l^{(1)} _{ij} ⇝ · · · ⇝ l^{(m-1)} _{ij}$ para todo par de vértices $i, j$. Computar cada entrada da matriz requer tempo linear porque é o mínimo entre $n$ alternativas. Temos $O(n^2)$ pares e isso quer dizer que cada passo custa $O(n^3)$. Temos ao todo n − 1 passos até conseguir obter os menores caminhos com até $n − 1$ arestas, totalizando $O(V^4)$. Podemos melhorar esse custo ao observar que esse processo iterativo é similar à multiplicação de matrizes e, portanto, podemos “dobrar” sucessivamente a quantidade de arestas consideradas e encontrar $l^{(n-1)} _{ij}$ em menos passos, totalizando $O(V^3 log \; n)$.

5.8.1 Algoritmo de Floyd-Warshall¶

Este algoritmo melhora a definição recursiva de custo de um caminho mínimo ao considerar quais vértices intermediários podem aparecer em um caminho mínimo. Se fixamos um vértice intermediário como $k$, teremos $p : u ⇝ p_{1} \;k ⇝ p_{2} \;v$. Veja que os vértices intermediários que aparecem no subcaminho $p_1$ não podem ser $k$ (mesma coisa para $p_2$). Dessa forma, podemos melhorar um custo de caminho que considere $\{1, ..., k\}$ como vértice intermediário se já tivermos calculado os custos ótimos de caminhos que considerem $\{1, ..., k − 1\}$ como intermediário:

Na notação do pseudocódigo abaixo, $w_{uv}$ corresponde a $G.W[u][v]$ e $d^{(k)}_{uv}$ corresponde a $D_k[u][v]$. Veja que agora continuamos com um algoritmo iterativo sobre matrizes, mas cada passo de refinamento requer custo constante e não linear. Portanto, temos $O(n)$ iterações e cada uma custa $O(n^2)$, totalizando $O(n^3)$.

FLOYD-WARSHALL(G)
// argumentos:
// G: grafo com vértices V e matriz de pesos G.W (n x n)

D_0 = G.W                          // caso base: nenhum vértice intermediário
for k = 1 to n
   D_k = nova matriz (n x n)
   for u = 1 to n
      for v = 1 to n
         D_k[u][v] = min(D_{k-1}[u][v], D_{k-1}[u][k] + D_{k-1}[k][v])
return D_n

Veja que podemos melhorar esse custo de espaço do algoritmo de $O(n^3)$ para $O(n^2)$. Podemos reconstruir também os caminhos mínimos além dos custos ótimos ao armazenar em outra matriz $Π$ quais decisões a cada passo levaram ao melhor custo. Uma alternativa é guardar o índice do predecessor do vértice que levou ao melhor custo: $Π^{(0)}$ considera como predecessores as arestas isoladas.

5.8.2 Algoritmo de Johnson¶

5.9 Fluxo máximo¶

Alguns conceitos importantes em fluxo máximo: entender as premissas do problema como conservação e skew, entender o conceito de cortes nessas redes, entender que o fluxo máximo é limitado superiormente por qualquer corte nessa rede, entender o conceito de redes residuais, entender que um caminho em uma rede residual que vai da origem até o destino indica que a rede admite mais fluxo e que portanto, a função ainda não está maximizada.

Propriedade da conservação do fluxo. Para cada vértice na rede que não for nem a fonte nem o destino, a quantidade de fluxo chegando no vértice deve ser igual à quantidade de fluxo saindo do vértice

Propriedade da restrição de capaciidade. Para cara par de vértices da rede, a quantidade de fluxo passando entre eles não pode ultrapassar a capacidade:

FORD-FULKERSON(G(V, E), s, t)
// argumentos:
// G(V, E): rede de fluxo com vértices V, arestas E
// s: vértice fonte
// t: vértice destino
// ao final, cada aresta contem seu fluxo em e.f

G_f = rede residual a partir de G
while existe caminho de aumento p em G_f de s a t
   delta = min { c_f(u, v) : (u, v) in p }
   for each (u, v) in p
      e = (u, v)
      if e in G.E
         e.f = e.f + delta
      else
         e = (v, u)
         e.f = e.f - delta
   atualize a rede residual G_f ao longo do caminho p

5.10 Exercícios¶

1 (crls 3ed. – 24.1.5) Dado um grafo direcionado com pesos nas arestas $G(V, E), w : E → \R$. Forneça um algoritmo $O(V E)$ que encontre, para cada vértice v, o valor δ∗(v) = minu∈V {δ(u, v)}.

Descrição de algoritmo: Vamos substituir o procedimento RELAX do algoritmo de Bellman-Ford pelo procedimento RELAX-MIN abaixo. Outra modificação, é inicializar os predecessores de cada vértices como eles próprios: $u.\pi \gets u$ para todo $u ∈ V$ . Veja que o último passo é necessário e coerente, já que $δ(u, u) = 0$ e portanto, representa um limite superior para a função em cada vértice.

RELAX-MIN(u, v, w)
// argumentos:
// u: vértice de origem
// v: vértice de destino
// w: função de peso das arestas

if v.d > MIN(w(u, v), u.d + w(u, v))
   v.d = MIN(w(u, v), u.d + w(u, v))
   v.pi = u.pi // o predecessor de v é o predecessor de u: u ou u' != u

2 (crls 3ed. – 24.1.6) Suponha que um grafo direcionado $G(V, E)$ e com pesos nas arestas contenha um ciclo de peso negativo. Forneça um algoritmo eficiente para listar os vértices desse ciclo.

Ideia de algoritmo: faça um caminhamento em profundidade (DFS) no grafo mantendo a soma dos pesos acumulados no caminho. Se o caminhamento encontrar uma aresta de volta (back edge), então um ciclo foi encontrado e tem-se também a soma dos pesos do ciclo. Ao detectar esse ciclo negativo, interrompemos o caminhamento imprimindo os vértices do caminho de volta à raíz, isto é, nas voltas da recursão até o destino da aresta de volta encontrada. Isso pode ser implementado:

(1) executando o Bellman-Ford; (2) marcando $u.d ← −∞$ para vértices alcançáveis através de vértices do ciclo negativo (DFS); (3) fazendo um novo DFS para detectar ciclo a partir de vértices cuja estimativa seja u.d = −∞; se encontrar aresta de volta (back-edge, cinza) significa que um ciclo foi detectado.

5.11 Grafos Eulerianos e Hamiltonianos¶

Conceitos importantes: caminhos e ciclos eulerianos, teorema que argumenta que em um grafo euleriano todo vértice tem grau par, algoritmo de Fleury que constrói um ciclo euleriano.

5.11.1 Definições importantes¶

• Percurso: coleção de vértices que são sequencialmente adjacentes

• Caminho: percurso em um grafo direcionado com todas as arestas no sentido início-fim do percurso.

• Percurso simples: não repete ligações.

• Percurso elementar: não repete vértices.

• Ciclo: percurso elementar fechado.

• Circuito: caminho elementar fechado – ciclo orientado.

5.11.2 Grafos eulerianos¶

Teorema 5.1. Um grafo $G = (V, E)$ não direcionado e conexo possui um ciclo euleriano se, e somente se, todos os seus vértices tiverem grau par.

Prova: Para $\Rarr$ devemos observar que em um ciclo precisamos ter uma forma de entrar e sair de cada vértice, ou seja, pelo menos uma quantidade par de arestas incidentes a cada um deles. Para $\Larr$ devemos fazer por indução no número de arestas. Todo grafo conexo cujos graus dos vértices forem todos ≥ 2 possui um percurso fechado: basta escolher iterativamente para cada vértice duas arestas, uma para entrada e uma para saída. Vamos considerar o percurso fechado de maior tamanho. Ao retirar as arestas desse percurso fechado do grafo, temos dois casos: ou todas as arestas foram retiradas e o percurso em questão é por si só um ciclo euleriano (percurso fechado que não repete arestas), ou sobraram algumas arestas formando uma componente também com todos os vértices de grau par – cada vértice tem seu grau diminuído de duas unidades, já que estamos retirando um percurso fechado. Se a componente restante tem vértices com grau par apenas e ela tem arestas, então novamente podemos dizer que existe um percurso fechado. Isso é um absurdo, já que poderíamos combinar esse novo percurso fechado com o percurso fechado inicial e máximo que teríamos um percurso fechado maior ainda, contradizendo a premissa. Em suma, podemos visualizar um ciclo euleriano (percurso fechado com todas as arestas) como uma decomposição disjunta das arestas em vários ciclos.

CICLO-EULERIANO-FLEURY(G(V, E))
// argumentos:
// G(V, E): grafo euleriano com vértices V e arestas E

seja s in V um vértice inicial qualquer
u = s // vértice corrente no percurso
while existirem arestas no grafo
   if d(u) == 1 // grau de u
      escolha a única aresta possível (u, v) in E
   else
      escolha (u, v) in E tal que mesmo que (u, v) seja removida,
                       s continua na mesma componente do restante das arestas
   adicione (u, v) ao percurso
   remova a aresta (u, v) do grafo
   u = v
retorne a sequência de arestas

CARTEIRO-CHINES(G(V, E))
// argumentos:
// G(V, E): grafo com vértices V e arestas E

if G nao-euleriano
   seja I o subconjunto de V dos vertices de grau impar
   for each u in I
      descubra os caminhos minimos d_uv a partir de u // usando Dijkstra, por exemplo
      d_uu = infinity
   P = pares de vertices u, v in I cuja soma das distancias d_uv seja minima // Algoritmo hungaro
   for each (u, v) in P
      adicionar aresta artificial (u, v) em G com custo d_uv
C = CICLO-EULERIANO-FLEURY(G(V, E))
for each aresta artificial (u, v) in C
   substitua em C a aresta (u, v) pelo caminho minimo u -> v
retorne C

CARTEIRO-CHINES-DIRECIONADO(G(V, E))
// argumentos:
// G(V, E): grafo direcionado com vértices V e arestas E

if G nao-euleriano
   seja S o subconjunto de V dos vertices u tal que d+(u) - d-(u) > 0
   seja T o subconjunto de V dos vertices u tal que d+(u) - d-(u) < 0
   for each u in S
      descubra os caminhos minimos d_uv a partir de u para todo v in T // Algoritmo Dijkstra
      d_uu = infinity
   S' = REPLICA-VERTICES(S) // w^(u) denota uma copia de u in S
   T' = REPLICA-VERTICES(T) // w^(u) denota uma copia de u in T
   PREENCHE-DISTANCIAS-REPLICAS(S', T', S, T)
   P = pares u in (S union S'), v in (T union T') cuja soma das distancias d_uv seja minima // Algoritmo hungaro
   for each (w, z) in P
      if w e replica w^(r) entao u = r senao u = w
      if z e replica z^(r) entao v = r senao v = z
      adicionar aresta artificial (u, v) em G com custo d_uv
C = CICLO-EULERIANO-FLEURY(G(V, E))
for each aresta artificial (u, v) in C
   substitua em C a aresta (u, v) pelo caminho minimo u -> v
retorne C

REPLICA-VERTICES(V)
// argumentos:
// V: conjunto de vértices

V' = {}
for each u in V
   for i = 2 to |d+(u) - d-(u)|
      seja w^(u) uma copia de u
      V' = V' union {w^(u)}
retorne V'

PREENCHE-DISTANCIAS-REPLICAS(S', T', S, T)
// argumentos:
// S', T': conjuntos de vértices replicados
// S, T: conjuntos de vértices originais

for each w^(u) in S'
   for each z^(v) in T'
      d_{w^(u)z^(v)} = d_uv
for each w^(u) in S'
   for each v in T
      d_{w^(u)v} = d_uv
for each u in S
   for each z^(v) in T'
      d_{uz^(v)} = d_uv

Algumas características importantes do algoritmo que resolve o problema do carteiro chinês:

• Se trata de um algoritmo de complexidade polinomial: algoritmo húngaro e chamadas do algoritmo de Djkstra continuam sendo polinomiais.
  

• Quando organizamos os vértices de grau ímpar em um grafo não euleriano em pares, isso sempre é seguro já que para qualquer grafo devemos ter uma quantidade par de vértices com grau ímpar: senão a soma dos graus não seria par e sabemos que isso é verdade.
  

• Se um grafo é euleriano já sabemos exatamente qual é o custo mínimo da instância: exatamente a soma dos pesos de cada aresta.
  

• Se um grafo não é euleriano, será inevitável passar por algumas arestas mais de uma vez e isso é capturado pelas arestas artificiais adicionadas: passar por uma aresta artificial (u, v) no percurso é equivalente a um percurso de mesmo custo que usa apenas arestas do grafo original: $u...v$.

5.11.3 Grafos hamiltonianos¶