Kruskal AJUDA

[ankmartins]

Boas pessoal

Tenho um trabalho para entregar ate sabado a noite, que consiste criar o algoritmo kruskal em java.

onde o algoritmo nos diz, que temos que ordenar os vertices em ordem crescente e escolher os seus n-1 primeiros vertices(onde o n é o numero de vertices) sem poder criar ciclo e dps no final nos dara o caminho de custo minimo.

o meu problema consiste que ele ao selecionar os n-1 vertices, cria ciclo, e isso não pode acontecer=/ já ando a matar a cabeça de volta disto a uns dias e não consigo resolver este problema, e o tempo esta se acabar =/

Abaixo deixo a função criada de modo a resolver o algoritmo kruskal,

//----------------Algoritmo Kruskal----------------
    public String Algoritmo_kruskal() {
        int valmax = matriz.length;
        String camfinal = "";
        int custototal = 0;
        for (int max = 1; max < 10; max++) {
            //----Ira verificar as linhas e as colunas
            for (int linha = 0; linha < matriz.length; linha++) {
                for (int coluna = 0; coluna < matriz.length; coluna++) {
                    //----Aqui verifica se é a aresta de menor custo
                    if (matriz[linha][coluna] > 0 && matriz[linha][coluna] == max) {
                        //----Adiciona o custo da aresta, de modo no final mostra o custo total
                        custototal = custototal + matriz[linha][coluna];
                        //----Aqui ira mostra ao utilizador as arestas que  formam o curso minino, de ordem crescente
                        if (coluna > linha) {
                            
                            camfinal = camfinal.concat("(" + (linha + 1) + ",");
                            camfinal = camfinal.concat((coluna + 1) + ") ");
                        } else {
                           
                            camfinal = camfinal.concat("(" + (coluna + 1) + ",");
                            camfinal = camfinal.concat((linha + 1) + ") ");
                        }
                        //--- Como o vertice não tem caminho para ele proprio mete o custo a zero
                        matriz[coluna][linha] = 0;
                        valmax--;
                    }
                        //---Aqui faz a operação n-1, onde o n é o numero de vertices, onde depois faz terminar o programa ao achar caminho já completo
                    if (valmax == 1) {
                        coluna = matriz.length;
                        linha = matriz.length;
                        max = 10;
                    }
                }
            }
        }
        return camfinal + ("\n Custo Mínimo total de " + custototal + ".\n ");
    }

Exemplo de um resultado.

0 1 4 3 7 2

1 0 3 6 6 1

4 3 0 0 7 0

3 6 0 0 0 0

7 6 7 0 0 2

2 1 0 0 2 0

---------- 1- Algoritmo de Kruskal----------

(1,2) (2,6) (1,6) (5,6) (1,4)

Custo Mínimo total de 9.

Se repararem cria ciclo do 1 para o 6, ou vice-versa.

pff ajudm me =/

cumps

Editado Maio 22, 2009 por ankmartins