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 nao pode acontecer=/ ja ando a matar a cabeça de volta disto a uns dias e nao consigo resolver este problema, e o tempo esta se acabar =/
Abaixo deixo a função criada de modo a resolver o algoritmo kruskal,
[code]
//----------------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 nao 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 ja completo
if (valmax == 1) {
coluna = matriz.length;
linha = matriz.length;
max = 10;
}
}
}
}
return camfinal + ("\n Custo Mínimo total de " + custototal + ".\n ");
}[/code]
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
