Você está aqui: Java ::: Estruturas de Dados ::: Grafos |
Como criar um grafo em Java - Estruturas de dados em Java para iniciantesQuantidade de visualizações: 882 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. ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- package estudos; // definição da classe que representa uma aresta // em um grafo. Aresta em inglês é edge. Uma aresta // faz a ligação entre dois vértices (vertex em inglês) public class Aresta { private Vertice origem; private Vertice destino; private int peso; // construtor da classe Aresta public Aresta(Vertice origem, Vertice destino, int peso) { this.origem = origem; this.destino = destino; this.peso = peso; } public Vertice getOrigem() { return origem; } public void setOrigem(Vertice origem) { this.origem = origem; } public Vertice getDestino() { return destino; } public void setDestino(Vertice destino) { this.destino = destino; } public int getPeso() { return peso; } public void setPeso(int peso) { this.peso = peso; } } 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. ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- package estudos; // definição da classe que representa um vértice // em um grafo. Vértice em inglês é vertex. Um // vértice é ligado a outro vértice por meio de // uma aresta (edge em inglês) import java.util.ArrayList; public class Vertice { private String cidade; private ArrayList<Aresta> arestas; // construtor da classe Vertice public Vertice(String nomeCidade){ this.cidade = nomeCidade; this.arestas = new ArrayList(); } // método que permite adicionar uma nova aresta a // este vértice public void adicionarAresta(Vertice destino, int peso){ this.arestas.add(new Aresta(this, destino, peso)); } // método que permite remover um aresta deste vértice public void removerAresta(Vertice destino){ this.arestas.removeIf(aresta -> aresta.getDestino().equals( destino)); } // método que exibe todas as arestas deste vértice public void exibir(boolean mostrarPeso){ String resultado = ""; // este vértice não possui arestas if (this.arestas.isEmpty()){ System.out.println(this.getCidade() + " --> (Vazio)"); } // possui arestas else{ // vamos percorrer as arestas deste vértice for(int i = 0; i < this.arestas.size(); i++){ // é a primeira aresta? if(i == 0){ // guardamos a origem resultado += this.arestas.get(i).getOrigem().getCidade() + " --> "; } // guardamos os destinos resultado += this.arestas.get(i).getDestino().getCidade(); // devemos mostrar os pesos das arestas? if(mostrarPeso){ resultado += " (" + this.arestas.get(i).getPeso() + ")"; } // ainda não é a última aresta if(i != this.arestas.size() - 1){ resultado += ", "; } } // e mostramos todas as arestas deste vértice System.out.println(resultado); } } public String getCidade() { return cidade; } public void setCidade(String cidade) { this.cidade = cidade; } public ArrayList<Aresta> getArestas() { return arestas; } public void setArestas(ArrayList<Aresta> arestas) { this.arestas = arestas; } } 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. ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- package estudos; // Definição da classe Grafo, que possui uma ArrayList de // vértices e duas variáveis boleanas indicando se ele // possui pesos (é valorado) e se é ou não dirigido import java.util.ArrayList; public class Grafo { private ArrayList<Vertice> vertices; private boolean valorado; private boolean dirigido; // construtor da classe Grafo public Grafo(boolean valorado, boolean dirigido) { this.vertices = new ArrayList(); this.valorado = valorado; this.dirigido = dirigido; } // método que permite adicionar um novo vértice e // e retorná-lo ao chamador public Vertice adicionarVertice(String cidade){ // cria o novo vértice Vertice novo = new Vertice(cidade); // adiciona o vértice na lista de vértices this.vertices.add(novo); // retorna o novo vértice return novo; } // método que permite adicionar uma aresta entre dois // vértices public void adicionarAresta(Vertice v1, Vertice v2, int peso){ // adicionamos a aresta no primeiro vértice v1.adicionarAresta(v2, peso); // é um digrafo? if(!this.isDirigido()){ // adicionamos a aresta no segundo vértice também v2.adicionarAresta(v1, peso); } } // método que permite remover uma aresta entre dois // vértices public void removerAresta(Vertice v1, Vertice v2){ // remove a aresta do primeiro vértice v1.removerAresta(v2); // é um grafo dirigido? if(!this.isDirigido()){ // remove a aresta do segundo vértice também v2.removerAresta(v1); } } // remove um vértice da lista de vértices public void removerVertice(Vertice v){ this.vertices.remove(v); } // método que busca e retorna um vértice baseado // em seu valor public Vertice buscarVerticeValor(String cidade){ for(Vertice v : this.vertices){ if(v.getCidade() == cidade){ return v; } } return null; } // método que exibe os vértices deste grafo public void exibirVertices(){ for(Vertice v : this.vertices){ v.exibir(this.valorado); } } public ArrayList<Vertice> getVertices() { return vertices; } public void setVertices(ArrayList<Vertice> vertices) { this.vertices = vertices; } public boolean isDirigido() { return dirigido; } public void setDirigido(boolean dirigido) { this.dirigido = dirigido; } public boolean isValorado() { return valorado; } public void setValorado(boolean valorado) { this.valorado = valorado; } } 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. ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- package estudos; public class Estudos { public static void main(String[] args) { // vamos criar um grafo valorado e dirigido Grafo grafo = new Grafo(true, true); // vamos adicionar os vértices Vertice goiania = grafo.adicionarVertice("Goiânia"); Vertice cuiaba = grafo.adicionarVertice("Cuiabá"); Vertice manaus = grafo.adicionarVertice("Manaus"); Vertice belem = grafo.adicionarVertice("Belém"); // agora ligamos os vértices por meio de suas arestas grafo.adicionarAresta(goiania, cuiaba, 850); grafo.adicionarAresta(goiania, belem, 1740); grafo.adicionarAresta(manaus, goiania, 730); grafo.adicionarAresta(belem, manaus, 420); // e exibimos o grafo grafo.exibirVertices(); } } 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: |
Java ::: Coleções (Collections) ::: Stack |
Java Collections - Como adicionar novos elementos a uma Stack JavaQuantidade de visualizações: 9030 vezes |
Elementos são adicionados a uma pilha (um objeto da classe Stack) por meio do método push(). Veja sua assinatura:public E push(E item) Veja um trecho de código no qual adicionamos três elementos à pilha: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- package arquivodecodigos; import java.util.*; public class Estudos{ public static void main(String args[]){ // Cria uma Stack de String Stack<String> pilha = new Stack<>(); System.out.println("Tamanho da pilha antes: " + pilha.size()); // adiciona três elementos na pilha pilha.push("Cuiabá"); pilha.push("Goiânia"); pilha.push("Belo Horizonte"); System.out.println("Tamanho da pilha agora: " + pilha.size()); } } Ao executarmos este código Java nós teremos o seguinte resultado: Tamanho da pilha antes: 0 Tamanho da pilha agora: 3 |
Java ::: Classes e Componentes ::: JComboBox |
Como classificar os itens de um JComboBox do Java Swing em ordem alfabéticaQuantidade de visualizações: 10324 vezes |
Este exemplo mostra como ordenar os itens de um JComboBox do Java Swing. A melhor forma de fazer isso é ordenando o array de strings antes de passá-lo para o construtor da classe JComboBox. Se novos itens forem inseridos em tempo de execução, a melhor saída é extender a classe DefaultComboBoxModel e fornecer tal funcionalidade. Veja o código Java completo para o exemplo: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- package estudos; import java.awt.*; import javax.swing.*; import java.util.*; public class Estudos extends JFrame{ public Estudos(){ super("A classe JComboBox"); Container c = getContentPane(); c.setLayout(new FlowLayout(FlowLayout.LEFT)); // Cria o array que armazenará os itens do // combo box String[] nomes = {"Osmar", "Cristina", "Antônio", "Marcela", "Joaquim"}; // ordena os itens Arrays.sort(nomes); // Cria o JComboBox JComboBox combo = new JComboBox(nomes); // Adiciona o JComboBox à janela c.add(combo); setSize(350, 250); setVisible(true); } public static void main(String args[]){ Estudos app = new Estudos(); app.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); } } |
Java ::: Coleções (Collections) ::: ArrayList |
Como inserir um item em uma determinada posição da ArrayList do Java usando o método add()Quantidade de visualizações: 14744 vezes |
Nesta dica mostrarei como é possível usar o método add() da classe ArrayList do Java para inserir um elemento em uma determinada posição, ou seja, em um determinado índice da lista. Para isso nós só precisamos usar a assinatura do método add() que aceita também o índice no qual o novo elemento será inserido. Veja:---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- public void add(int index, E element) Você deve ter em mente, claro, que este método pode disparar uma exceção do tipo IndexOutOfBoundsException se o índice informado estiver fora da faixa permitida. Veja agora o código Java completo para o exemplo: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- package estudos; import java.util.ArrayList; public class Estudos{ public static void main(String[] args){ // cria uma ArrayList que conterá strings ArrayList<String> pessoas = new ArrayList<>(); // adiciona itens na lista pessoas.add("Alberto"); pessoas.add("Victor"); pessoas.add("João"); // adiciona um item na posição 2, depois de Victor pessoas.add(2, "Ricardo"); // exibe os itens da lista for(int i = 0; i < pessoas.size(); i++){ System.out.println(pessoas.get(i)); } System.exit(0); } } Ao executar este código Java nós teremos o seguinte resultado: Alberto Victor Ricardo João |
Desafios, Exercícios e Algoritmos Resolvidos de Java |
Veja mais Dicas e truques de Java |
Dicas e truques de outras linguagens |
Códigos Fonte |
Software de Gestão Financeira com código fonte em PHP, MySQL, Bootstrap, jQuery - Inclui cadastro de clientes, fornecedores e ticket de atendimento Diga adeus às planilhas do Excel e tenha 100% de controle sobre suas contas a pagar e a receber, gestão de receitas e despesas, cadastro de clientes e fornecedores com fotos e histórico de atendimentos. Código fonte completo e funcional, com instruções para instalação e configuração do banco de dados MySQL. Fácil de modificar e adicionar novas funcionalidades. Clique aqui e saiba mais |
Controle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidades Tenha o seu próprio sistema de controle de estoque web. com cadastro de produtos, categorias, fornecedores, entradas e saídas de produtos, com relatórios por data, margem de lucro e muito mais. Código simples e fácil de modificar. Acompanha instruções para instalação e criação do banco de dados MySQL. Clique aqui e saiba mais |
Linguagens Mais Populares |
1º lugar: Java |