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
