Possible bug in Prim's algorithm

[gordicaleksa]

It seems that by always taking the lowest cost edge like this:
final Graph.Edge<Integer> e = edgesAvailable.remove();
, without checking if it is still connecting us to the unvisited vertex we will end up with cycles.
When I added these lines of code in my project:
while (!unvisited.contains(e.getToVertex())) { e = edgesAvailable.remove(); }
It performs well. I've implemented my own Graph, Edge and Vertex class which should behave the same as these used in this project, maybe I'm missing something. Worth checking it out.

[gokberksahin]

Yeah i encountered same issue, added these lines for possibility of a cycle.

for (int i = 0; i < edgesAvailable.size(); i++) { if (!unvisited.contains(edgesAvailable.get(i).getDestinition())) edgesAvailable.remove(edgesAvailable.get(i)); }

[phishman3579]

I'll gladly fix this in master branch if you can provide a unit test which shows the bug.

[phishman3579]

Has anyone come up with a good unit test for this bug?

[KannanSnair]

Let me work on it