Skip to content

Latest commit

 

History

History

Centro-e-Diametro

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

Centro e Diâmetro

Algoritmo que encontra o centro e o diâmetro de um grafo em $\mathcal{O}(N + M)$ com duas BFS.

Definição: O centro de um grafo é igual ao subconjunto de nodos com excentricidade mínima. A excentricidade de um nodo é a maior distância dele para qualquer outro nodo. Em outras palavras, pra um nodo ser centro do grafo, ele deve minimizar a maior distância para qualquer outro nodo.

O diâmetro de um grafo é a maior distância entre dois nodos quaisquer.