Ir ao conteúdo

Posts recomendados

Postado

Meu Main:

 

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package main;

import java.util.Scanner;
import kruskalprim.Grafo;
import kruskalprim.KruskalPrim;

/**
 *
 * @author cieco
 */
public class Main {
    
    public static void main(String[] args) {
        KruskalPrim k = new KruskalPrim();
        System.out.print("Você quer um grafo com quantos vértices? ");
        Scanner ler = new Scanner(System.in);
        int numVert = ler.nextInt();
        Grafo g = new Grafo(numVert);
        int ind1, ind2, ind3 = 0, peso;
        for(ind1 = 0; ind1 < g.getNumeroVertices(); ind1++){
            for(ind2 = ind1 + 1; ind2 < g.getNumeroVertices(); ind2++){
                do{
                    System.out.print("Peso da aresta de " + ind1 + " para " + ind2 + ": ");
                    peso = ler.nextInt();
                }while(peso < 0);
                g.getAresta(ind3).setAresta(ind1, ind2, peso);
                g.getAresta(ind3).setAresta(ind2, ind1, peso);
                ind3++;
            }
        }
        k.fazerKruskal(g);
        for(ind1 = 0; ind1 < k.getArvore().numeroArestas(); ind1++) if(k.getArvore().getAresta(ind1).getPeso() > 0){
            System.out.println("Aresta entre " + k.getArvore().getAresta(ind1).getV1() + " e " + 
                    k.getArvore().getAresta(ind1).getV2() + " com peso " + k.getArvore().getAresta(ind1).getPeso());
        }
    }
    
}

 

Meu Grafo:

 

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package kruskalprim;

/**
 *
 * @author cieco
 */
public class Grafo {
    private Aresta are[];
    private int numeroVertices = -1;
    
    public Grafo(int numVert){
        if(numVert > 1){
            this.numeroVertices = numVert;
            this.are = new Aresta[(this.numeroVertices * (this.numeroVertices - 1)) / 2];
        }
    }
    
    public int numeroArestas(){
        return are.length;
    }
    
    public Aresta getAresta(int pos){
        return are[pos];
    }
    
    public int getNumeroVertices(){
        return this.numeroVertices;
    }
}

 

Meu Aresta:

 

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package kruskalprim;

/**
 *
 * @author cieco
 */
public class Aresta {
    private int v1, v2, peso;
    
    public void setAresta(int v1, int v2, int peso){
        if(peso >= 0){
            this.v1 = v1;
            this.v2 = v2;
            this.peso = peso;
        }
    }
    
    public int getV1(){
        return v1;
    }
    
    public int getV2(){
        return v2;
    }
    
    public int getPeso(){
        return peso;
    }
}

 

Meu KruskalPrim:

 

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package kruskalprim;

/**
 *
 * @author cieco
 */
public class KruskalPrim {
    
    private Grafo arvore;

    public void fazerKruskal(Grafo g) {
        arvore = g;
        int i, j, k, aux;
        boolean trocou;
        boolean visitados[] = new boolean[arvore.getNumeroVertices()];
        int vetPesos[] = new int[arvore.getNumeroVertices()];
        for (i = 0; i < arvore.getNumeroVertices(); i++) {
            vetPesos[i] = arvore.getAresta(i).getPeso();
        }
        //ordenação QuadrosSort
        do{
            trocou = false;
            for(i = 0; i < arvore.getNumeroVertices() - 1; i++) if(vetPesos[i] > vetPesos[i + 1]){
                aux = vetPesos[i];
                vetPesos[i] = vetPesos[i + 1];
                vetPesos[i + 1] = aux;
                trocou = true;
            }
        }while(trocou);
        for(i = 0; i < arvore.getNumeroVertices(); i++){
            visitados[i] = true;
            for(j = 0; j < arvore.numeroArestas(); j++) for(k = 0; k < arvore.numeroArestas(); k++){
                if(vetPesos[j] == arvore.getAresta(k).getPeso()){
                    if(visitados[arvore.getAresta(k).getV2()]){
                        arvore.getAresta(k).setAresta(arvore.getAresta(k).getV1(), arvore.getAresta(k).getV2(), 0);
                        arvore.getAresta(k).setAresta(arvore.getAresta(k).getV2(), arvore.getAresta(k).getV1(), 0);
                    }
                }
            }
        }
    }
    
    public Grafo getArvore(){
        return arvore;
    }
}

 

Qual é o meu problema?

Crie uma conta ou entre para comentar

Você precisa ser um usuário para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...

LANÇAMENTO!

eletronica2025-popup.jpg


CLIQUE AQUI E BAIXE AGORA MESMO!