Introdução à Grafos

Muitas aplicações de computação necessitam considerar conjuntos de conexões entre pares de objetos:

  • Existe um caminho para ir de um objeto a outro seguindo as conexões?
  • Qual a menor distância entre um objeto e outro?
  • Quantos outros objetos podem ser alcançados a partir de um objeto?

Grafos são utilizados para modelar tais problemas e são possivelmente, as estruturas matemáticas mais utilizadas pela ciência.

Algumas aplicações:

  • Auxiliar o GPS na escolha da melhor rota de viagem
  • Ajudar na busca em sites da web e etc;

Grafos consistem de dois conjuntos V e E e uma função x, tal que:

  • V(G) é um conjunto finito e não vazio de vértices. Os vértices são objetos simples, que podem ter uma chave e outros atributos;
  • A(G) é um conjunto disperso de arcos ou arestas x, é um conjunto de funções que associam pares de vértices V(G).
  • Definição matemática: G =(V(G), E(G), X)

Exemplo:

G =(V(G), E(G), X) onde :

V(G) = {1,2,3,4,5,6}

E(G) = {e^1, e^2,e^3, e^4, e^5}

x = (e^1) = (1,2) , (e^2) = (1,4) ,

x = (e^3) = (2,3) , (e^4) = (2,5) ,

x = (e^5) = (3,4)

Exemplos de Grafos:

Este post foi apenas um introdutório à grafos que é um assunto muito extenso, porém bem interessante de entender como funciona. Sugiro que pesquisem mais sobre o assunto. Aqui vai um link que irá ajudar vocês, tanto a aprender quanto à implementar os algorismos.

Link : http://www2.dcc.ufmg.br/livros/algoritmos-java/cap7/transp/completo4/cap7.pdf

“Takuno é foda, o resto é moda.”

Bons estudos.