Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM5 - problemas em grafos - Coggle Diagram
MM5 - problemas em grafos
Depth First Search (DFS)
Explora o grafo começando de um vertex "x", e vai até o nó mais profundo. Depois volta e explora outro vizinho não visitado.
Utiliza um vetor global de inteiros, pra guardar o estado de cada vertex (visited ou unvisited)
Tempo de execução:
O(V + E) com lista de adjacência
O(V²) com matriz de adjacência
A ordem dos vizinhos influencia a sequência de visitação, o que pode mudar resultados em problemas que exigem ordem específica
Exemplo: Dominator:
Determinar se um vértice X domina Y, ou seja, se todos os caminhos de 0 até Y passam por X
Distinguir tree/back/cross edges
Ao executar DFS, obtemos uma árvore geradora DFS (DFS spanning tree), e com ela podemos classificar cada aresta em um de três tipos principais
Tree Edge: Conecta um vértice u explorado a um vizinho v ainda não visitado.
Back Edge: Conecta um vértice u a um ancestral ainda em exploração (forma ciclo).
Forward/Cross Edge: Conecta u (já finalizado ou explorado) a um vértice já visitado.
Detectar ciclos em grafos direcionados e não direcionados.
Base para algoritmos de detecção de ciclos, topological sort e SCC
Para detectar se um grafo é cíclico, basta verificar se há back edge
BFS
Percorre o grafo em camadas. Começa em um vértice e visita todos os vizinhos do primeiro nível, depois do segundo, etc
Calcula automaticamente a distância mínima (número de camadas), que é útil em problemas de shortest path sem pesos
Também roda em O(V + E) com lista de adjacência
Pode ser adaptado para verificar conectividade, bipartição e níveis em árvores
Ideal para grafos não ponderados. E se houver pesos, usar Dijkstra
Testar se o grafo é 2-colorível (Grafo bipartido)
Também pode ser feito com DFS, mas a BFS facilita alternar as camadas
Para grafos desconectados, é preciso repetir a BFS em cada componente
Guarde a coloração em color[] e use valores 0 e 1 (ou ±1)
Contar/rotular grupos conectados (grafos não direcionados)
Cada chamada de dfs(u) (ou bfs(u)) visita apenas os vértices conectados a u
Complexidade O(V + E)
Útil em detecção de subgrafos independentes
Achar vértices/arestas críticas
Bridge (cut edge): aresta cuja remoção desconecta o grafo
Analise cuidadosamente o caso raiz
Articulation Point (cut vertex): vértice cuja remoção aumenta o número de componentes conectadosBridge (cut edge): aresta cuja remoção desconecta o grafo.
Colorir e medir regiões conectadas
Variante de DFS/BFS usada em grafos implícitos
Rotula (“colore”) regiões conectadas
Aplicações incluem:
Contagem de regiões (ex: “Wetlands of Florida”).
Segmentação de imagens.
Jogos tipo “pintar território”.
Evitr recursão profunda em grids grandes. Melhor BFS iterativo
Agrupar vértices mutuamente alcançáveis
Em um grafo direcionado, os SCCs podem ser colapsados em vértices únicos formando um DAG
Problemas comuns de aplicação:
Detectar “componentes de confiança” (redes sociais).
Simplificar grafos em DAGs.
Resolver dependências circulares.
Um SCC (Strongly Connected Component) é um subgrafo onde todo par (u, v) tem caminho de u → v e v → u
Topological Sort
Ordenação linear de vértices de um DAG tal que se existe uma aresta u → v, então u vem antes de v
Aplicação: Ordenar pré-requisitos de disciplinas ou tarefas
DFS (pós-ordem) ou Kahn (graus de entrada); detectar ciclos