Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
Coleção de vértices ligados por arestas
Adjacentes quando ligados por uma aresta não direcionada
Quando o gráfico é direcionado (dígrafo), temos tail e head
Quando todos os vértices estão conectados, o grafo está completo
Pode estar denso (muitas ligações) ou escasso
Grafo com pesos
Arestas tem pesos diferentes
Acíclico: Não há ciclos (Quando uma caminho começa e termina no mesmo vértice sem passar por uma aresta duas vezes)
Busca exaustiva
BFS
Visita todos os vértices adjacentes e depois os vértices adjacentes aos vértices adjacentes
Fila é usada para armazenar o resultado da operação
A medida que são adicionados, são marcados como visitados
No fim, os vértices vão sendo removidos da fila
Eficiência
V² para matriz e V + A (arestas) para listas
DFS
Prossegue para o próximo nó adjacente não visitado
Quando não há mais vértices adjacentes não visitados volta para o primeiro adjacente
Encerra quando retorna ao início
Se restar vértices não visitados, recomeça por um desses
Forma uma floresta
Usar uma pilha para organizar o resultado
O vértice é mandado para stack quando for alcançado pela primeira vez
e popped quando se torna um beco sem saída
Eficiência
V² para matriz e V + A (arestas) para listas
A cada interação o vértice é marcado como visitado
BFS consegue checar conectividade e ciclicidade, como o DFS
BFS não acha pontos de articulação, DFS sim
BFS consegue encontrar o menor caminho
Ordenação topológica
DFS realizada em um grafo acíclico direcionado (dag)
Lista pré-requisitos na ordem que precisam ser atendidos
Se não for dag não é possível fazer
Se um beco sem saída é encontrado, não é dag
decrease-and-conquer (segundo método)
Identifica o inicial (sem arestas chegando)
Deleta, assim como suas arestas
Se houver várias possibilidades, define arbitrariamente
Se não houver nenhum, não há solução
Há várias soluções alternativas
Representação
Matriz: Os índices serão os vértices
Matriz quadrada nxn sendo n o número de vértices
Lista ligada: Array de listas
Cada posição é um vértice e a lista contém suas ligações
Caminho
Simples: Todos os vértices são distintos
Tamanho é o número de vértices -1 ou o número de arestas
Direcionado: Grafo é direcionado e há um sentido para percorrer os vértices.