Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos e Algoritmos de Busca - Coggle Diagram
Grafos e Algoritmos de Busca
Grafos
Representações
Lista de adjacência
Matriz de adjacência: n × n
Conceitos chave
Grafo conexo: existe caminho entre todos os pares de vértices
Árvore: grafo conexo e acíclico
Grafo acíclico: não contém ciclos
Floresta: conjunto de árvores desconexas
Ciclo (Cycle): caminho que começa e termina no mesmo vértice
Grafo completo: todos os vértices conectados entre si
Caminho (Path): sequência de vértices conectados
Grafo ponderado: arestas com peso (custo)
Definição
Grafo não dirigido: arestas sem direção (u, v) ≡ (v, u)
Digrafo (Grafo dirigido): arestas com direção (u → v)
Grafo G = (V, E) com V = vértices e E = arestas
DFS e BFS
BFS – Breadth-First Search
BFS Forest
Tree edges: como no DFS
Cross edges: entre níveis iguais ou adjacentes
Aplicações
Conectividade
Checar aciclicidade
Caminho com menor número de arestas
Usa fila
Visita vértices por níveis (1º vizinhos, depois vizinhos dos vizinhos...)
DFS – Depth-First Search
Usa pilha (explícita ou recursão)
DFS Forest
Tree edges: exploram vértices novos
Back edges: voltam a ancestrais → indicam ciclos
Vai o mais fundo possível antes de recuar
Aplicações
Checar conectividade
Verificar ciclos (presença de back edge)
Componentes conexas
Topological Sorting
Só funciona se o grafo for DAG
Detecta ciclos → se houver back edge → não é DAG
DFS + Stack
Executa DFS
Adiciona vértices ao stack ao “morrer” (dead-end)
Inverte a ordem do stack → ordenação topológica
Definição
Ordenar vértices de um digrafo acíclico (DAG)
Para cada aresta (u → v), u vem antes de v
Remoção de fontes
Ordem de remoção é a ordenação topológica
Se não houver fonte e ainda houver vértices → tem ciclo
Remove iterativamente vértices sem arestas de entrada
Aplicações
Compiladores (ordem de instruções)
Planilhas (dependência de células)
Resolução de símbolos (linkagem)
Agendamento de tarefas com pré-requisitos