Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM7 - Coggle Diagram
MM7
Grafos
Definição
Vértices (nodes)
Arestas (edges)
Não orientado vs direcionado
Representações
Matriz de adjacência
Listas de adjacência
Grafos ponderados
Matriz de custos (∞ se não há aresta)
Peso em listas
Caminhos e ciclos
Caminho simples vs não simples
Ciclo e grafo acíclico
Conectividade
Grafo conectado vs componentes
Componentes máximas
Ordenação Topológica
Objetivo: ordenar vértices de um DAG com respeito às direções
Aplicações: pré-requisitos, agendamento, compilação, PERT/CPM
Algoritmo via DFS
Executa DFS, coleta no “pop” e reverte a ordem
Detecta ciclos via arestas de retorno
Algoritmo por remoção de fontes
Remove vértices sem entradas repetidamente
Ordem de remoção = ordenação
Propriedades:
Todo DAG tem ao menos uma fonte
Possui múltiplas soluções possíveis
Busca Exaustiva
DFS (Depth‑First Search)
Usa pilha (recursão ou explícita)
Pseudocódigo e execução
DFS‑Forest: arestas de árvore vs de retorno
Aplicações:
Verificar conectividade
Detectar ciclos
Pontos de articulação (avançado)
Complexidade:
Matriz: Θ(|V|²)
Lista: Θ(|V| + |E|)
BFS (Breadth‑First Search)
Usa fila
Pseudocódigo e execução
BFS‑Forest: arestas de árvore vs cruzadas
Aplicações:
Verificar conectividade
Encontrar caminho com mínimo de arestas
Complexidade:
Matriz: Θ(|V|²)
Lista: Θ(|V| + |E|)