# Grafos (Graph Algorithms)

### 📌 Visão Geral

**Grafos** são estruturas de dados fundamentais que modelam relações entre objetos. Um grafo consiste em **vértices (nós)** conectados por **arestas (edges)**. Algoritmos de grafos resolvem problemas como encontrar caminhos, fluxo máximo, árvores geradoras mínimas e ordenação topológica.

```
Vértice (Nó) → ●
Aresta (Edge) → ───

Grafo exemplo:    ●───●
                 /     \
                ●───●   ●
```

#### Analogia

> *"Grafos são como mapas rodoviários: as cidades são vértices, as estradas são arestas. Algoritmos de grafos respondem perguntas como 'qual o caminho mais curto?', 'existe rota?', 'como otimizar o fluxo de tráfego?'."*

***

### 🏷️ Tipos de Grafos

| Tipo                      | Descrição                   | Exemplo                        |
| ------------------------- | --------------------------- | ------------------------------ |
| **Direcionado (Digrafo)** | Arestas têm direção         | Twitter (seguir ≠ ser seguido) |
| **Não Direcionado**       | Arestas são bidirecionais   | Facebook (amizade mútua)       |
| **Ponderado**             | Arestas têm pesos (custos)  | Distâncias, tempos, custos     |
| **Não Ponderado**         | Todas as arestas têm peso 1 | Relações simples               |
| **Cíclico**               | Contém ciclos               | Redes de cidades               |
| **Acíclico (DAG)**        | Sem ciclos                  | Dependências de tarefas        |
| **Conectado**             | Todos vértices alcançáveis  | Rede de computadores           |
| **Desconectado**          | Múltiplos componentes       | Ilhas isoladas                 |

***

### 📋 Algoritmos por Categoria

#### 🛣️ Caminho Mínimo (Shortest Path)

| Algoritmo          | Complexidade   | Pesos Negativos | Ciclos Negativos | Uso Principal                  |
| ------------------ | -------------- | --------------- | ---------------- | ------------------------------ |
| **Dijkstra**       | O((V+E) log V) | ❌ Não           | ❌ Não            | GPS, redes (padrão)            |
| **Bellman-Ford**   | O(V × E)       | ✅ Sim           | ✅ Detecta        | Detecção de ciclos negativos   |
| **Floyd-Warshall** | O(V³)          | ✅ Sim           | ✅ Detecta        | Todos os pares (grafos densos) |

#### 🌳 Árvore Geradora Mínima (MST)

| Algoritmo   | Complexidade   | Melhor para     | Uso                      |
| ----------- | -------------- | --------------- | ------------------------ |
| **Prim**    | O((V+E) log V) | Grafos densos   | Redes de cabos, estradas |
| **Kruskal** | O(E log E)     | Grafos esparsos | Conexão de componentes   |

#### 🌊 Fluxo em Redes (Max Flow)

| Algoritmo          | Complexidade      | Uso                        |
| ------------------ | ----------------- | -------------------------- |
| **Ford-Fulkerson** | O(E × fluxo\_max) | Fluxo máximo, corte mínimo |

#### 📊 Ordenação Topológica

| Algoritmo      | Complexidade | Uso                                   |
| -------------- | ------------ | ------------------------------------- |
| **Kahn (BFS)** | O(V + E)     | Dependências de tarefas, compiladores |

#### 🏆 Ranqueamento

| Algoritmo    | Complexidade         | Uso                   |
| ------------ | -------------------- | --------------------- |
| **PageRank** | O(V + E) × iterações | Busca na web (Google) |

***

### 🔢 Algoritmos em Detalhe

#### 1. Dijkstra (Caminho Mais Curto)

**Como funciona:** Encontra o menor caminho da origem a todos os vértices (pesos positivos).

```python
import heapq

def dijkstra(grafo, origem):
    # grafo: dict {vértice: [(vizinho, peso), ...]}
    distancias = {v: float('inf') for v in grafo}
    distancias[origem] = 0
    heap = [(0, origem)]
    visitados = set()
    
    while heap:
        dist_atual, v = heapq.heappop(heap)
        
        if v in visitados:
            continue
        visitados.add(v)
        
        for vizinho, peso in grafo[v]:
            distancia = dist_atual + peso
            if distancia < distancias[vizinho]:
                distancias[vizinho] = distancia
                heapq.heappush(heap, (distancia, vizinho))
    
    return distancias

# Exemplo
grafo = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 1), ('D', 5)],
    'C': [('D', 8)],
    'D': []
}
distancias = dijkstra(grafo, 'A')
print(distancias)  # {'A':0, 'B':4, 'C':2, 'D':9}
```

| Vantagem                      | Desvantagem                        |
| ----------------------------- | ---------------------------------- |
| ✅ Muito rápido O((V+E) log V) | ❌ Não funciona com pesos negativos |
| ✅ Ótimo para GPS e redes      |                                    |

**Quando usar:** Pesos positivos, fonte única.

***

#### 2. Bellman-Ford

**Como funciona:** Relaxa todas as arestas V-1 vezes. Detecta ciclos negativos.

```python
def bellman_ford(grafo, vertices, origem):
    # grafo: lista de (origem, destino, peso)
    distancias = {v: float('inf') for v in vertices}
    distancias[origem] = 0
    
    # Relaxar arestas V-1 vezes
    for _ in range(len(vertices) - 1):
        for u, v, peso in grafo:
            if distancias[u] + peso < distancias[v]:
                distancias[v] = distancias[u] + peso
    
    # Detectar ciclos negativos
    for u, v, peso in grafo:
        if distancias[u] + peso < distancias[v]:
            return None  # Ciclo negativo detectado
    
    return distancias

# Exemplo
vertices = ['A', 'B', 'C', 'D']
arestas = [
    ('A', 'B', 4), ('A', 'C', 2),
    ('B', 'C', 1), ('B', 'D', 5),
    ('C', 'D', 8)
]
distancias = bellman_ford(arestas, vertices, 'A')
print(distancias)  # {'A':0, 'B':4, 'C':2, 'D':9}
```

| Vantagem                   | Desvantagem         |
| -------------------------- | ------------------- |
| ✅ Aceita pesos negativos   | ❌ Mais lento O(V×E) |
| ✅ Detecta ciclos negativos |                     |

**Quando usar:** Pesos negativos, detecção de ciclos.

***

#### 3. Floyd-Warshall (Todos os Pares)

**Como funciona:** Matriz de distâncias, testa todos os vértices como intermediários.

```python
def floyd_warshall(grafo, vertices):
    n = len(vertices)
    idx = {v: i for i, v in enumerate(vertices)}
    
    # Inicializar matriz de distâncias
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    
    for u, v, peso in grafo:
        dist[idx[u]][idx[v]] = peso
    
    # Algoritmo principal
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

# Exemplo
arestas = [('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1), ('B', 'D', 5), ('C', 'D', 8)]
vertices = ['A', 'B', 'C', 'D']
matriz = floyd_warshall(arestas, vertices)
```

| Vantagem                  | Desvantagem                         |
| ------------------------- | ----------------------------------- |
| ✅ Encontra todos os pares | ❌ O(V³) (lento para grafos grandes) |
| ✅ Simples de implementar  |                                     |

**Quando usar:** Grafos densos (V < 500), necessidade de todas as distâncias.

***

#### 4. Prim (Árvore Geradora Mínima)

**Como funciona:** Constrói a MST adicionando o vértice mais próximo.

```python
import heapq

def prim(grafo, vertices):
    # grafo: dict {vértice: [(vizinho, peso), ...]}
    inicio = vertices[0]
    visitados = set([inicio])
    heap = [(peso, inicio, vizinho) for vizinho, peso in grafo[inicio]]
    heapq.heapify(heap)
    
    mst = []
    custo_total = 0
    
    while heap and len(visitados) < len(vertices):
        peso, u, v = heapq.heappop(heap)
        
        if v not in visitados:
            visitados.add(v)
            mst.append((u, v, peso))
            custo_total += peso
            
            for vizinho, p in grafo[v]:
                if vizinho not in visitados:
                    heapq.heappush(heap, (p, v, vizinho))
    
    return mst, custo_total

# Exemplo
grafo = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8)],
    'D': [('B', 5), ('C', 8)]
}
mst, custo = prim(grafo, ['A', 'B', 'C', 'D'])
print(f"MST: {mst}, Custo total: {custo}")  # Custo = 7 (A-C-B-D)
```

| Vantagem                 | Desvantagem              |
| ------------------------ | ------------------------ |
| ✅ Rápido O((V+E) log V)  | ❌ Requer grafo conectado |
| ✅ Bom para grafos densos |                          |

**Quando usar:** Redes de cabos, estradas (minimizar custo total).

***

#### 5. Kruskal (Árvore Geradora Mínima)

**Como funciona:** Ordena arestas por peso, adiciona se não formar ciclo.

```python
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, rank, x, y):
    rx, ry = find(parent, x), find(parent, y)
    if rx != ry:
        if rank[rx] < rank[ry]:
            parent[rx] = ry
        elif rank[rx] > rank[ry]:
            parent[ry] = rx
        else:
            parent[ry] = rx
            rank[rx] += 1
        return True
    return False

def kruskal(arestas, vertices):
    # Ordenar arestas por peso
    arestas.sort(key=lambda x: x[2])
    
    parent = {v: v for v in vertices}
    rank = {v: 0 for v in vertices}
    
    mst = []
    custo_total = 0
    
    for u, v, peso in arestas:
        if union(parent, rank, u, v):
            mst.append((u, v, peso))
            custo_total += peso
    
    return mst, custo_total

# Exemplo
arestas = [('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1), ('B', 'D', 5), ('C', 'D', 8)]
vertices = ['A', 'B', 'C', 'D']
mst, custo = kruskal(arestas, vertices)
print(f"MST: {mst}, Custo total: {custo}")  # Custo = 7
```

| Vantagem                   | Desvantagem                   |
| -------------------------- | ----------------------------- |
| ✅ Bom para grafos esparsos | ❌ Requer ordenação O(E log E) |
| ✅ Fácil de implementar     |                               |

**Quando usar:** Muitos vértices, poucas arestas.

***

#### 6. Ford-Fulkerson (Fluxo Máximo)

**Como funciona:** Encontra caminhos de aumento (DFS/BFS) até não haver mais.

```python
from collections import deque

def bfs(capacidade, source, sink, parent):
    visited = set()
    queue = deque([source])
    visited.add(source)
    
    while queue:
        u = queue.popleft()
        for v in range(len(capacidade)):
            if v not in visited and capacidade[u][v] > 0:
                visited.add(v)
                parent[v] = u
                if v == sink:
                    return True
                queue.append(v)
    return False

def ford_fulkerson(capacidade, source, sink):
    parent = [-1] * len(capacidade)
    fluxo_maximo = 0
    
    while bfs(capacidade, source, sink, parent):
        # Encontrar gargalo
        path_flow = float('inf')
        s = sink
        while s != source:
            path_flow = min(path_flow, capacidade[parent[s]][s])
            s = parent[s]
        
        # Atualizar capacidades residuais
        v = sink
        while v != source:
            u = parent[v]
            capacidade[u][v] -= path_flow
            capacidade[v][u] += path_flow
            v = parent[v]
        
        fluxo_maximo += path_flow
    
    return fluxo_maximo

# Exemplo: Rede de fluxo (0=source, 5=sink)
capacidade = [
    [0, 16, 13, 0, 0, 0],  # 0
    [0, 0, 10, 12, 0, 0],  # 1
    [0, 4, 0, 0, 14, 0],   # 2
    [0, 0, 9, 0, 0, 20],   # 3
    [0, 0, 0, 7, 0, 4],    # 4
    [0, 0, 0, 0, 0, 0]     # 5
]
fluxo = ford_fulkerson(capacidade, 0, 5)
print(f"Fluxo máximo: {fluxo}")
```

| Vantagem                     | Desvantagem                         |
| ---------------------------- | ----------------------------------- |
| ✅ Resolve fluxo máximo       | ❌ Pode ser lento (depende do fluxo) |
| ✅ Base para muitos problemas |                                     |

**Quando usar:** Redes de comunicação, logística, alocação de tarefas.

***

#### 7. Kahn (Ordenação Topológica - BFS)

**Como funciona:** Remove vértices com grau de entrada zero.

```python
from collections import deque

def ordenacao_topologica_kahn(grafo, vertices):
    # Calcular grau de entrada
    grau_entrada = {v: 0 for v in vertices}
    for u in grafo:
        for v in grafo[u]:
            grau_entrada[v] += 1
    
    # Fila com vértices de grau zero
    fila = deque([v for v in vertices if grau_entrada[v] == 0])
    resultado = []
    
    while fila:
        u = fila.popleft()
        resultado.append(u)
        
        for v in grafo[u]:
            grau_entrada[v] -= 1
            if grau_entrada[v] == 0:
                fila.append(v)
    
    if len(resultado) != len(vertices):
        return None  # Ciclo detectado
    
    return resultado

# Exemplo: Dependências de tarefas
grafo = {
    'A': ['C'],      # A → C
    'B': ['C', 'D'], # B → C, B → D
    'C': ['E'],      # C → E
    'D': ['F'],      # D → F
    'E': [],
    'F': []
}
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
ordem = ordenacao_topologica_kahn(grafo, vertices)
print(f"Ordem topológica: {ordem}")  # ['A', 'B', 'C', 'D', 'E', 'F'] ou similar
```

| Vantagem              | Desvantagem                   |
| --------------------- | ----------------------------- |
| ✅ Simples e intuitivo | ❌ Requer grafo acíclico (DAG) |
| ✅ Detecta ciclos      |                               |

**Quando usar:** Agendamento de tarefas, resolução de dependências.

***

#### 8. PageRank (Google)

**Como funciona:** Ranqueia vértices baseado na importância das conexões.

```python
def pagerank(grafo, vertices, damping=0.85, iteracoes=100):
    n = len(vertices)
    idx = {v: i for i, v in enumerate(vertices)}
    
    # Matriz de transição
    matriz = [[0] * n for _ in range(n)]
    for u in grafo:
        if grafo[u]:
            for v in grafo[u]:
                matriz[idx[v]][idx[u]] = 1 / len(grafo[u])
    
    # Vetor PageRank inicial
    pr = [1/n] * n
    
    for _ in range(iteracoes):
        novo_pr = [(1-damping)/n] * n
        for i in range(n):
            for j in range(n):
                novo_pr[i] += damping * matriz[i][j] * pr[j]
        pr = novo_pr
    
    return {v: pr[i] for v, i in idx.items()}

# Exemplo: Rede de páginas web
grafo = {
    'A': ['B', 'C'],
    'B': ['C'],
    'C': ['A'],
    'D': ['C']
}
vertices = ['A', 'B', 'C', 'D']
pr = pagerank(grafo, vertices)
for pagina, score in sorted(pr.items(), key=lambda x: x[1], reverse=True):
    print(f"{pagina}: {score:.4f}")
```

| Vantagem                   | Desvantagem         |
| -------------------------- | ------------------- |
| ✅ Ranqueia por importância | ❌ Cálculo iterativo |
| ✅ Base do Google original  |                     |

**Quando usar:** Ranqueamento de páginas web, análise de redes sociais.

***

### 📊 Comparação de Complexidades

| Algoritmo          | Tempo           | Espaço | Tipo           |
| ------------------ | --------------- | ------ | -------------- |
| **Dijkstra**       | O((V+E) log V)  | O(V)   | Caminho mínimo |
| **Bellman-Ford**   | O(V × E)        | O(V)   | Caminho mínimo |
| **Floyd-Warshall** | O(V³)           | O(V²)  | Caminho mínimo |
| **Prim**           | O((V+E) log V)  | O(V)   | MST            |
| **Kruskal**        | O(E log E)      | O(V)   | MST            |
| **Ford-Fulkerson** | O(E × fluxo)    | O(V)   | Fluxo máximo   |
| **Kahn**           | O(V + E)        | O(V)   | Topológica     |
| **PageRank**       | O((V+E) × iter) | O(V)   | Ranqueamento   |

***

### 🎯 Guia de Seleção

#### "Preciso encontrar o menor caminho..."

| Se seu problema é...                    | Use                |
| --------------------------------------- | ------------------ |
| GPS, rota mais rápida (pesos positivos) | Dijkstra           |
| Pesos podem ser negativos               | Bellman-Ford       |
| Preciso de todas as distâncias          | Floyd-Warshall     |
| Grafos grandes, poucas consultas        | Dijkstra da origem |

#### "Preciso conectar tudo com custo mínimo..."

| Se seu problema é...             | Use     |
| -------------------------------- | ------- |
| Grafos densos (muitas arestas)   | Prim    |
| Grafos esparsos (poucas arestas) | Kruskal |

#### "Preciso maximizar fluxo..."

| Se seu problema é... | Use            |
| -------------------- | -------------- |
| Rede de comunicação  | Ford-Fulkerson |
| Alocação de tarefas  | Ford-Fulkerson |

#### "Preciso ordenar tarefas dependentes..."

| Se seu problema é...    | Use  |
| ----------------------- | ---- |
| Compilação de código    | Kahn |
| Agendamento de projetos | Kahn |

***

### 🔗 Links Úteis

* [Visualgo - Graph Algorithms](https://visualgo.net/en)
* [Graph Algorithms (Stanford)](https://web.stanford.edu/class/cs97si/08-graph-algorithms.pdf)
* [NetworkX - Python Graph Library](https://networkx.org/)

***

### 📚 Representações de Grafos

| Representação            | Espaço | Acesso  | Uso                           |
| ------------------------ | ------ | ------- | ----------------------------- |
| **Matriz de Adjacência** | O(V²)  | O(1)    | Grafos densos                 |
| **Lista de Adjacência**  | O(V+E) | O(grau) | Grafos esparsos (recomendado) |
| **Lista de Arestas**     | O(E)   | O(E)    | Algoritmos como Kruskal       |

```python
# Lista de Adjacência (recomendada)
grafo = {
    'A': [('B', 5), ('C', 3)],
    'B': [('D', 2)],
    'C': [('B', 1)],
    'D': []
}

# Matriz de Adjacência (para V pequeno)
matriz = [
    [0, 5, 3, 0],
    [0, 0, 0, 2],
    [0, 1, 0, 0],
    [0, 0, 0, 0]
]

# Lista de Arestas (para algoritmos de MST)
arestas = [
    ('A', 'B', 5),
    ('A', 'C', 3),
    ('B', 'D', 2),
    ('C', 'B', 1)
]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://0xmorte.gitbook.io/bibliadopentestbr/conceitos/algoritmos/grafos-graph-algorithms.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.