Você está aqui: Java ::: Estruturas de Dados ::: Grafos |
Como criar um grafo em Java - Estruturas de dados em Java para iniciantesQuantidade 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 segundosQuantidade 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.ObjectCollectionQuantidade 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 ifQuantidade 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 iniciantesQuantidade 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 |
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 |