Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM5, Capítulo 4 — Grafos - Coggle Diagram
-
Capítulo 4 — Grafos
4.2 Travessia de Grafos
DFS (Depth First Search)
- Comportamento: exploração em profundidade + backtracking
- Implementação: recursiva, vetor dfs_num (UNVISITED/VISITED)
- Complexidade: O(V+E) (Lista) / O(V^2) (Matriz)
- Ordem de vizinhos influencia visitação
- Detecção de alcance, componentes, toposort (pós-ordem)
- Base para Tarjan (SCC), articulações e pontes
- Exemplo: UVa 11902 - Dominator (algoritmo O(V^3) / otimizações)
-
-
-
Topological Sort (DAG)
- Objetivo: ordenar vértices com respeito às arestas dirigidas
- Algoritmo via DFS (pós-ordem -> reverter) — Tarjan
- Algoritmo Kahn (BFS modificado): enfileirar vértices com indegree=0
- Observações: várias ordenações possíveis; comportamento em grafos com ciclos
Verificação Bipartido
- Checagem 2-cores (0/1) via BFS (ou DFS)
- Conflito de cor → não bipartido
- Ex.: UVa 10004 - Bicoloring
-
-
-
-
-
-
Visão Geral e Motivação
- Problemas: travessias, MST, SSSP/APSP, fluxos, grafos especiais
- Público: ICPC (abrangente) / IOI (subconjunto)
- Pressupostos: termos da Tabela 4.1; representações: Matriz, Lista, Edge List, grafo implícito