Oi Pessoal.
Galera é um seguinte, eu to desesperado.
Preciso urgente de um exemplo de código java para arvore geradora minima, pode ser em método prim ou krustal.
Alguém se dispoem a me ajudar
Ja passei horas na net procurando e nada encontro que compile corretamente.
Deixa eu te contar um segredo: se você tivesse passado essas horas que procurou um pronto fazendo, provavelmente já estaria pronto. E saberia o assunto, ainda por cima, ao contrário do que acontece com o código copiado.
Existe o google também:
http://www.cs.columbia.edu/~gskc/Code/AdvancedInternetServices/MinimalSpanningTree/Kruskal.java
http://students.ceid.upatras.gr/~papagel/project/prim.htm
Detalhe: Bastou procurar por Kruskal Java ou por Prim Java.
Oi Vini.
Entaum, é o que eu disse existe possíveis códigos, porém não compilam.
O mesmo acontece com o exemplo que vc me passou nesse link
[quote=macielpereira]Oi Vini.
Entaum, é o que eu disse existe possíveis códigos, porém não compilam.
O mesmo acontece com o exemplo que vc me passou nesse link[/quote]
Cara eu acabei de pegar o código aqui e compilar. Foi numa boa.
Qual a interface que vc está usando? Poste a saida do erro aqui no fórum.
[]s
Olá MLimaCarlos
Eu estou usando o netbbeans 6.8
O código compila, porem nada acontece além dessa mensagem aqui
run:
Running [Kruskal] - 2000
Usage: java Kruskal
CONSTRUÍDO COM SUCESSO (tempo total: 0 segundos)
Cara eu sou muito fraco em java, e to precisando fazer esse código rodar. se poder me ajudar eu agradeço de coração.
Segue o código aew.
[code]import java.io.;
import java.util.;
public class Kruskal {
private final int MAX_NODES = 21;
private HashSet nodes[]; // Array of connected components
private TreeSet allEdges; // Priority queue of Edge objects
private Vector allNewEdges; // Edges in Minimal-Spanning Tree
public static void main(String args[]) {
System.out.println(“Running [Kruskal] - 2000”);
if (args.length != 1) {
System.out.println("Usage: java Kruskal ");
System.exit(0);
}
Kruskal k = new Kruskal();
k.readInGraphData(args[0]);
k.performKruskal();
k.printFinalEdges();
}
Kruskal() {
// Constructor
nodes = new HashSet[MAX_NODES]; // Create array for components
allEdges = new TreeSet(new Edge()); // Create empty priority queue
allNewEdges = new Vector(MAX_NODES); // Create vector for MST edges
}
private void readInGraphData(String fileName) {
try {
FileReader file = new FileReader(fileName);
BufferedReader buff = new BufferedReader(file);
String line = buff.readLine();
while (line != null) {
StringTokenizer tok = new StringTokenizer(line, " ");
int from = Integer.valueOf(tok.nextToken()).intValue();
int to = Integer.valueOf(tok.nextToken()).intValue();
int cost = Integer.valueOf(tok.nextToken()).intValue();
allEdges.add(new Edge(from, to, cost)); // Update priority queue
if (nodes[from] == null) {
// Create set of connect components [singleton] for this node
nodes[from] = new HashSet(2*MAX_NODES);
nodes[from].add(new Integer(from));
}
if (nodes[to] == null) {
// Create set of connect components [singleton] for this node
nodes[to] = new HashSet(2*MAX_NODES);
nodes[to].add(new Integer(to));
}
line = buff.readLine();
}
buff.close();
} catch (IOException e) {
//
}
}
private void performKruskal() {
int size = allEdges.size();
for (int i=0; i<size; i++) {
Edge curEdge = (Edge) allEdges.first();
if (allEdges.remove(curEdge)) {
// successful removal from priority queue: allEdges
if (nodesAreInDifferentSets(curEdge.from, curEdge.to)) {
// System.out.println("Nodes are in different sets ...");
HashSet src, dst;
int dstHashSetIndex;
if (nodes[curEdge.from].size() > nodes[curEdge.to].size()) {
// have to transfer all nodes including curEdge.to
src = nodes[curEdge.to];
dst = nodes[dstHashSetIndex = curEdge.from];
} else {
// have to transfer all nodes including curEdge.from
src = nodes[curEdge.from];
dst = nodes[dstHashSetIndex = curEdge.to];
}
Object srcArray[] = src.toArray();
int transferSize = srcArray.length;
for (int j=0; j<transferSize; j++) {
// move each node from set: src into set: dst
// and update appropriate index in array: nodes
if (src.remove(srcArray[j])) {
dst.add(srcArray[j]);
nodes[((Integer) srcArray[j]).intValue()] = nodes[dstHashSetIndex];
} else {
// This is a serious problem
System.out.println("Something wrong: set union");
System.exit(1);
}
}
allNewEdges.add(curEdge);
// add new edge to MST edge vector
} else {
// System.out.println("Nodes are in the same set ... nothing to do here");
}
} else {
// This is a serious problem
System.out.println("TreeSet should have contained this element!!");
System.exit(1);
}
}
}
private boolean nodesAreInDifferentSets(int a, int b) {
// returns true if graph nodes (a,b) are in different
// connected components, ie the set for ‘a’ is different
// from that for ‘b’
return(!nodes[a].equals(nodes[b]));
}
private void printFinalEdges() {
System.out.println("The minimal spanning tree generated by "+
"\nKruskal’s algorithm is: ");
while (!allNewEdges.isEmpty()) {
// for each edge in Vector of MST edges
Edge e = (Edge) allNewEdges.firstElement();
System.out.println(“Nodes: (” + e.from + ", " + e.to +
") with cost: " + e.cost);
allNewEdges.remove(e);
}
}
class Edge implements Comparator {
// Inner class for representing edge+end-points
public int from, to, cost;
public Edge() {
// Default constructor for TreeSet creation
}
public Edge(int f, int t, int c) {
// Inner class constructor
from = f; to = t; cost = c;
}
public int compare(Object o1, Object o2) {
// Used for comparisions during add/remove operations
int cost1 = ((Edge) o1).cost;
int cost2 = ((Edge) o2).cost;
int from1 = ((Edge) o1).from;
int from2 = ((Edge) o2).from;
int to1 = ((Edge) o1).to;
int to2 = ((Edge) o2).to;
if (cost1<cost2)
return(-1);
else if (cost1==cost2 && from1==from2 && to1==to2)
return(0);
else if (cost1==cost2)
return(-1);
else if (cost1>cost2)
return(1);
else
return(0);
}
public boolean equals(Object obj) {
// Used for comparisions during add/remove operations
Edge e = (Edge) obj;
return (cost==e.cost && from==e.from && to==e.to);
}
}
}[/code]
Ele vai apresentar esta mensagem pois não há um evento definido na main.
Ou você chama este programa e passa parâmetros ou muda a main e faz com que as coisas aconteçam ou cria outra classe que chame os métodos que você quer.
Se mexe cara, vai à luta…
Bom vamos lá…
Dentro deste arquivo onde está escrito o seguinte código:
public static void main (String args[])
{
Kruskal k = new kruskal(); // inicializa o objeto
k.readInGraphData("Caminho do arquivo que vc deseja fazer a otimização"); // eu recomendo que vc coloque ele no mesmo pacote. Esse comando abre o arquivo pra leitura
k.performKruskal(); // executa o algoritmo no arquivo aberto
k.printFinalEdges(); // Imprime o resultado na tela.
}Mas , pelo - vc sabe o que esse codigo faz?
se sim ok!
[quote]
mlimacarlos [/quote]
não podemos dar respostas de mão dada !!! :evil:
[quote=lokit"s]Mas , pelo - vc sabe o que esse codigo faz?
se sim ok!
não podemos dar respostas de mão dada !!! :evil:[/quote]
infelizmente…
eu tive algoritmos de geração mínima numa matéria chamada pesquisa operacional.
O cara tava precisando… deixa o garoto ser feliz!
:twisted: