Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 4: Graphs Parte 1 - Coggle Diagram
Capítulo 4: Graphs Parte 1
4.1 Overview and Motivation
Objetivo:
Entender problemas de grafos e algoritmos associados.
Tipos de Grafos:
Vértices/Nodes → Entidades (pontos)
Arestas/Edges → Conexões
Ponderados (Weighted) e Não-Ponderados (Unweighted)
Dirigidos (Directed) e Não-dirigidos (Undirected)
Ciclo (Cycle) e Árvore/Floresta (Tree/Forest)
Multigrafo → múltiplas arestas
DAG → Grafo acíclico dirigido
Conceitos: Denso, Esparso, Euleriano, Bipartido, etc.
Aplicações:
Caminhos mínimos, fluxos, MSTs, conectividade, topologia, etc.
4.2.1 Depth First Search (DFS)
Ideia: Explorar o máximo possível antes de retroceder.
Complexidade: O(V + E)
Usa: pilha implícita (recursão)
Aplicações:
Componentes conectados
Topological Sort
Detectar ciclos
Articulation points, bridges
SCC (Strongly Connected Components)
4.2.2 Breadth First Search (BFS)
Ideia: Explora em camadas (níveis)
Usa: fila (queue)
Complexidade: O(V + E)
Usos:
Menor caminho em grafos não ponderados
Flood fill
Verificar conectividade
4.2.3 Finding Connected Components (Undirected Graph)
Objetivo: Encontrar subconjuntos de vértices conectados.
Método: Chamar DFS/BFS repetidamente em nós não visitados.
4.2.4 Flood Fill (Labeling/Coloring)
Aplicação clássica em grids (2D)
4.2.5 Topological Sort (DAG)
Usa: DFS ou Kahn’s Algorithm (BFS modificado)
Propriedade: Ordenação linear de vértices tal que todas as arestas vão de u → v com u antes de v.
4.2.6 Bipartite Graph Check
Verifica se o grafo pode ser 2-colorido sem conflito.
4.2.7 Graph Edge Property Check (DFS Spanning Tree)
Classifica arestas:
Tree edge: para um vértice não visitado.
Back edge: volta para um ancestral (forma ciclo).
Forward/Cross edge: alcança vértice já visitado, mas não ancestral.
Aplicação: Análise estrutural do grafo.
4.2.8 Articulation Points & Bridges
Usa: DFS com dfs_num e dfs_low.
Articulation Point: vértice cuja remoção desconecta o grafo.
Bridge: aresta cuja remoção desconecta.
Condição:
Para pontos: dfs_low[v] >= dfs_num[u]
Para pontes: dfs_low[v] > dfs_num[u]
4.2.9 Strongly Connected Components (SCC - Directed Graph)
Objetivo: Encontrar componentes onde todos os vértices são alcançáveis entre si.
Algoritmos:
Kosaraju: 2 DFS + grafo transposto
Tarjan: 1 DFS, usa dfs_low e pilha
Complexidade: O(V + E)