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: 457 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:

Delphi ::: Dicas & Truques ::: Rotinas de Conversão

Como converter uma string em um valor numérico de ponto-flutuante (com parte fracionária) em Delphi usando as funções StrToFloat(), TryStrToFloat() e StrToFloatDef()

Quantidade de visualizações: 24479 vezes
Em algumas situações precisamos converter strings em valores numéricos do tipo ponto-flutuante, ou seja, números que contenham uma parte fracionária. Isso acontece quando recebemos valores de caixas de texto e precisamos usuá-los em cálculos.

Vamos começar com a função StrToFloat() da unit SysUtils. Esta função recebe uma string representando um valor de ponto-flutuante válido e retorna um valor de ponto-flutuante. Veja o exemplo:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

procedure TForm1.Button1Click(Sender: TObject);
var
  valor1, valor2, soma: Double;
begin
  // vamos receber as strings dos TEdits e converter
  // seus valores para números de ponto-flutuante
  // note que em Delphi, um valor de ponto-flutuante
  // é informado em caixas de texto usando vírgula. Ex: 7,3
  valor1 := StrToFloat(Edit1.Text);
  valor2 := StrToFloat(Edit2.Text);

  // vamos obter a soma dos dois valores
  soma := valor1 + valor2;

  // vamos exibir o resultado. Note o uso de FloatToStr() para
  // converter o valor fracionário em string
  ShowMessage('A soma é: ' + FloatToStr(soma));
end;

Note que, se a string sendo convertida possuir um valor de ponto-flutuante inválido, uma exceção do tipo EConvertError será lançada. Podemos evitar isso usando a função TryStrToFloat(). Esta função recebe dois argumentos: a string a ser convertida e a variável do tipo Extended, Double ou Single que receberá o valor. O resultado será true se a conversão for feita com sucesso e false em caso contrário. Veja:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

procedure TForm1.Button1Click(Sender: TObject);
var
  valor: Double;
begin
  // vamos tentar converter o valor da caixa de texto
  // em um valor de ponto-flutuante
  if TryStrToFloat(Edit1.Text, valor) then
    ShowMessage('Conversão efetuada com sucesso.')
  else
    ShowMessage('Erro na conversão');
end;

Há ainda uma terceira possibilidade: usar a função StrToFloatDef(). Esta função funciona exatamente da mesma forma que StrToFloat(), exceto que agora, se houver um erro de conversão, um valor de ponto-flutuante padrão será retornado. Veja:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

procedure TForm1.Button1Click(Sender: TObject);
var
  valor: Double;
begin
  // vamos converter o valor da caixa de texto
  // em um valor de ponto-flutuante. Se a conversão não puder
  // ser feita o valor 10,50 será atribuído à varial valor
  valor := StrToFloatDef(Edit1.Text, 10.50);

  // vamos exibir o resultado
  ShowMessage(FloatToStr(valor));
end;

Para fins de compatibilidade, esta dica foi escrita usando Delphi 2009.


PHP ::: Dicas & Truques ::: Data e Hora

Datas e horas em PHP - Como obter o fuso horário em segundos

Quantidade de visualizações: 8146 vezes
Nesta dica veremos como usar date("Z") para retornar o fuso horário da nossa localidade em PHP. Lembre-se de que a função date() com o parâmetro "Z" retorna o fuso horário em segundos. Este valor reflete a diferença em segundos que estamos do Tempo Universal Coordenado (Coordinated Universal Time - UTC), também conhecido como tempo civil, e é o fuso horário de referência a partir do qual se calculam todas as outras zonas horárias do mundo.

Veja o código PHP completo para o exemplo:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

<html>
<head>
<title>Estudando PHP</title>
</head>
<body>
 
<?php
  $fuso_segundos = date("Z");
  $horas = ($fuso_segundos / 60) / 60;
  echo "O fuso horário em segundos é " .
    $fuso_segundos . " (" . $horas . " horas)";
?>
  
</body>
</html>

Ao executar este código nós teremos o seguinte resultado:

O fuso horário em segundos é 7200 (2 horas)


C# ::: Windows Forms ::: ComboBox

Como excluir todos os itens de um ComboBox do C# Windows Forms usando a função Clear() da classe ComboBox.ObjectCollection

Quantidade de visualizações: 9732 vezes
Há algumas situações nas quais precisamos remover (limpar) todos os itens de um ComboBox. Isso pode ser feito com uma chamada ao método Clear() da classe ComboBox.ObjectCollection. Temos acesso a esta classe por meio da propriedade Items da classe ComboBox. Vja o exemplo:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

private void button1_Click(object sender, EventArgs e){
  // exclui todos os itens do ComboBox chamado
  // linguagensCombo
  linguagensCombo.Items.Clear();
}



Lisp ::: Fundamentos da Linguagem ::: Estruturas de Controle

Como testar uma condição em Lisp usando a macro if

Quantidade de visualizações: 795 vezes
Nesta dica mostrarei como podemos usar a macro if da linguagem Common Lisp para testar uma condição. Por se tratar de um exemplo básico, não mostrarei um caminho alternativo, ou seja, a mensagem será exibido somente se a condição for satisfeita. Em outras dicas eu complemento com o desvio opcional.

Veja um exemplo no qual solicitamos um número ao usuário e informamos se o valor lido é maior que 10:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

; Vamos definir as variáveis que vamos
; usar no programa
(defvar numero)

; Este é o programa principal
(defun Estudos()
  ; Vamos ler o número
  (princ "Informe um número: ")
  ; talvez o seu compilador não precise disso
  (force-output)
  ; atribui o valor lido à variável numero
  (setq numero (read))
  
  ; vamos testar se este número é maior que 10
  (if (> numero 10)
    (format t "~D é maior que 10~%" numero))
  
  ; E mostramos o número informado
  (format t "O número informado foi: ~D" numero)
)

; Auto-executa a função Estudos()
(Estudos)

Ao executar este código Common Lisp nós teremos o seguinte resultado:

Informe um número: 12
12 é maior que 10
O número informado foi: 12


VB.NET ::: Fundamentos da Linguagem ::: Estruturas de Controle

Como usar o laço For do VB.NET - Apostila VB.NET para iniciantes

Quantidade de visualizações: 13239 vezes
O laço For...Next é usado quando sabemos exatamente a quantidade de vezes que o bloco de códigos deverá ser executado. Veja um exemplo no qual contamos de 1 a 10:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

For valor As Integer = 1 To 10 Step 1
  Console.WriteLine(valor)
Next

Veja que o laço For...Next é composto de três partes muito importantes:

a) Inicialização da variável de controle:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

For valor As Integer = 1

Aqui é onde definimos o valor inicial da variável de controle. No exemplo nós fizemos a declaração da variável no cabeçalho do laço, mas ela pode ser declarada externamente sem nenhum problema.

b) Limite do valor da variável de controle:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

To 10

A palavra-chave To permite definir o valor máximo que a variável de controle pode alcançar.

c) Incremento da variável de controle:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

Step 1

A palavra-chave Step permite definir o valor que servirá de incremento para a variável de controle. No exemplo usamos 1, mas poderia ser qualquer valor inteiro.

Veja um exemplo de laço For...Next no qual exibimos os números pares de 0 a 20:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

For numero As Integer = 0 To 20 Step 2
  Console.WriteLine(numero)
Next

E se quisermos contar de trás para frente? Fácil, basta fornecer um valor negativo para o incremento. Veja:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

For numero As Integer = 10 To 0 Step -1
  Console.WriteLine(numero)
Next



Desafios, Exercícios e Algoritmos Resolvidos de VB.NET

Veja mais Dicas e truques de VB.NET

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: Delphi
6º lugar: C
7º lugar: JavaScript
8º lugar: C++
9º lugar: VB.NET
10º lugar: Ruby



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