Boa noite pessoal, estou fazendo um trabalho sobre grafos, mas estou tendo grande problema com o algoritmo de Prim.
Eu consegui fazer um, mas esta vindo uma resposta que não é correta. Vocês poderiam me ajudar a encontrar o erro? Já estou trabalhando nesse a algoritmo há horas.
public Collection agmUsandoPrim(ImplementsGrafo g)
{
ArrayList t = new ArrayList();
ArrayList arestas = copiaArestas(g.getListaArestas());
Collections.sort(arestas);
ArrayList<Vertice> b = new ArrayList<Vertice>();
ArrayList<Vertice> V = copiaVertices(g.getListaVertices());
Collections.sort(V);
b.add(V.get(0));
while(b.size() != g.getNumV())
{
Aresta x = null;
for(Aresta a : arestas)
{
x = a;
if(!existeVertice(b, a.origem()) && existeVertice(b, a.destino())){
break;
}
}
arestas.remove(x);
if(x != null){
t.add(x);
b.add(x.origem());
}
}
O exemplo de grafo que estou usando é
5
0 0-40; 1-50;
1 1-45; 2-4;
2 3-1; 0-99;
3 1-42; 4-7;
4 3-78; 0-32;
//segunda linha: 0 0-40; 1-50;
duas arestas com origem 0, uma com destino 0 e peso 40 e outra com destino 1 e peso 50.
muito obrigado aos que tentarem a descobrir o porquê do meu algoritmo não retornar a resposta correta, já estou nesse problema há mais ou menos 4 horas.
