Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
Depth-First Search (DFS)
As aplicações elementares importantes do DFS incluem a verificação da conectividade e
verificar a aciclicidade de um gráfico.
Processo
- Inicia o percurso de um gráfico em um vértice arbitrário, marcando-o como visitado.
- Para cada iteração, o algoritmo prossegue para um vértice não visitado que é adjacente ao atual. Este processo continua até um beco sem saída (nenhum adjacente não visitado).
- No beco sem saída, o algoritmo recua uma aresta e tenta continuar o processo. O algoritmo é interrompido após retornar ao vértice inicial, sendo o último um beco sem saída.
- Se algum vértice ainda permanecer, o DFS deve começar em qualquer um deles.
DFS Stack
Rastreia o processo, empurrando o vértice para a pilha quando os vértices são alcançados pela primeira vez e removendo-o quando se tornar um beco sem saída
DFS Forest
-
Cada novo vértice visitado (primeira vez) é anexado como uma filho. Essa borda é chamada de Tree Edge.
-
-
Caminhos e ciclos
-
Se todos os vértices de um caminho forem distintos, o caminho é considerado simples.
O comprimento de um caminho é o número total de vértices nos vértices na sequência de vértices definindo o caminho menos 1. → Mesmo número de arestas!
-
Grafos Ponderados
-
Tem inúmeras aplicações do mundo real, como encontrar o caminho mais curto entre dois pontos em uma rede de transporte ou comunicação ou o problema do caixeiro viajante
-