Você está aqui: Java ::: Estruturas de Dados ::: Grafos

Como criar um grafo em Java - Estruturas de dados em Java para iniciantes

Quantidade 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 Java

Quantidade 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 que este método nos permite adicionar o elemento E no topo da pilha e ao mesmo tempo obter uma referência ao elemento adicionado. É claro que raramente esta referência é útil, mas é bom saber exatamente a operação fornecida pelo método.

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ética

Quantidade 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

Programa de Gestão Financeira Controle de Contas a Pagar e a Receber com Cadastro de Clientes e FornecedoresSoftware 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 funcionalidadesControle 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
2º lugar: Python
3º lugar: C#
4º lugar: PHP
5º lugar: C
6º lugar: Delphi
7º lugar: JavaScript
8º lugar: C++
9º lugar: VB.NET
10º lugar: Ruby



© 2025 Arquivo de Códigos - Todos os direitos reservados
Neste momento há 35 usuários muito felizes estudando em nosso site.