 |
|
Você está aqui: Java ::: Estruturas de Dados ::: Grafos |
||||
Como criar um grafo em Java - Estruturas de dados em Java para iniciantesQuantidade de visualizações: 1196 vezes |
||||
|
Depois de estudar as listas, pilhas, filas e árvores (binárias ou não), o estudo de grafos é a próxima etapa no campo das estruturas de dados. E nesta dica eu mostrarei a descrição da estrutura de dados grafo e como criá-la na linguagem Java, passo-a-passo. Grafos são estruturas de dados formadas por um conjunto de vértices e um conjunto de arestas. Os vértices são os nós e as arestas são responsáveis por fazer as ligações entre esses nós. Vértice em inglês é vertex, enquanto aresta é edge. Alguns autores também gostam de chamar a aresta de arco (no caso dos grafos dirigidos, que veremos mais adiante). Antes de prosseguirmos, vamos ver um exemplo de grafo:  Nesta imagem as cidades representam os vértices do grafo, enquanto as ligações entre elas são as arestas. Note que este é um grafo orientado, também chamado de dirigido ou digrafo, pois as arestas possuem uma direção. Dessa forma, a partir de Goiânia nós podemos ir para Cuiabá e Belém, sem caminho contrário. A partir de Belém podemos ir para Manaus e de Manaus para Goiânia. Veja que cada aresta possui um número associado. Em nosso caso, coloquei a distância entre as cidades (só como exemplo, é claro). Ao fazermos isso, cada aresta possui um peso, tornando o grafo um grafo valorado. Onde encontro exemplos e aplicações de grafos? Grafos são muito usados na representação de rotas de voos, grades curriculares, mapas de estradas, redes de computadores, mapas de metrô, relacionamento entre as pessoas em redes sociais, e muito mais. Algoritmos de percurso em grafos são estudados e aprimorados todos os dias. O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 1959, soluciona o problema do caminho mais curto em um grafo dirigido ou não dirigido com arestas de peso não negativo. Implementação de grafos em Java Vamos programar agora? A seguir eu mostro como podemos reproduzir em código Java o grafo de cidades que vimos acima. Para isso usaremos programação orientada a objetos e ArrayLists. Em resumo nós criaremos as classes Grafo, Vertice e Aresta e usaremos objetos ArrayList para guardar os vértices no grafo e relacionar as arestas de um determinado vértice. No código eu mostro como é possível combinar grafos dirigidos e não dirigidos na mesma implementação. Vamos começar? A classe Aresta Para começarmos, veja o código para a classe Aresta, que possui duas variáveis do tipo Vertice represetando o vértice de origem e o de destino. Na nossa aplicação, seriam a cidade de origem e a cidade de destino. A variável peso representa a distância (não verificada) entre elas.
A classe Vertice Agora que já temos a classe Aresta, vamos passar a para a classe Vertice, que representa cada cidade no nosso exemplo. A primeira coisa a observar é que a classe Vertice possui como variáveis o nome da cidade e uma ArrayList de arestas. Note também o método adicionarAresta(), que permite informar o vértice de destino e o peso da aresta. O método removerAresta() recebe o vértice de destino e remove a aresta correspondente. Finalmente o método exibir() permite exibir todas as arestas de um determinado vértice.
A classe Grafo Agora que já temos as classe Aresta e Vertice, vamos criar a classe Grafo. Comece observando que esta classe possui uma ArrayList de vértices e duas variáveis boleanas indicando se o grafo possui pesos (valorado) e se é dirigido (digrafo) ou não. O método adicionarVertice() recebe o nome da cidade e permite criar um novo vértice no grafo. O método adicionarAresta() recebe dois vértices e os liga por meio de uma aresta. Note também a passagem do peso para a aresta. Se o grafo for dirigido, a aresta é inserida tanto para o vértice de origem quanto para o vértice de destino. Temos ainda os métodos removerAresta(), removerVertice(), buscarVerticeValor() e exibirVertices(), todos devidamente comentados para facilitar o seu entendimento.
A classe de teste Para finalizar, veja o código para a classe principal que nos permite criar um grafo digirido, com pesos para as arestas e representando exatamente as ligações da figura acima. Experimente trocar os valores e veja os resultados interessantes que obtemos.
Ao executar este código Java completo nós teremos o seguinte resultado: Goiânia --> Cuiabá (850), Belém (1740) Cuiabá --> (Vazio) Manaus --> Goiânia (730) Belém --> Manaus (420) |
||||
 Link para compartilhar na Internet ou com seus amigos: |
||||
Desafios, Exercícios e Algoritmos Resolvidos de Java |
Veja mais Dicas e truques de Java |
Dicas e truques de outras linguagens |
E-Books em PDF |
||||
|
||||
|
||||
Linguagens Mais Populares |
||||
|
1º lugar: Java |
