Algoritmos de Grafos: Cálculo de Distâncias Médias, Minimização de Ruído e Identificação de Pontes Críticas
Page Hopping - UVA 821
Em um ambiente com N salas interconectadas (1≤N≤100), calculamos a distância média dos caminhos mais curtos entre todos os pares de salas alcençáveis. A entrada consiste em múltiplos casos de teste terminados com "0 0". Para cada caso, pares de inteiros indicam conexões diretas entre salas.
#include <iostream ...
Publicado em 7-14 18:47
Algoritmo de Tarjan para Análise de Grafos Direcionados
Componentes Fortemente Conexos
O algoritmo de Tarjan identifica componentes fortemente conexos (SCCs) em um grafo direcionado, permitindo a condensação subsequente. Utilizamos uma busca em profundidade (DFS) para construir uma árvore DFS, atribuindo a cada vértice u um tempo de descoberta ordem[u] e um valor menor[u] que representa o mener temp ...
Publicado em 6-20 21:31