Possible bug in Prim's algorithm
gordicaleksa opened this issue · 4 comments
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.
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)); }
I'll gladly fix this in master branch if you can provide a unit test which shows the bug.
Has anyone come up with a good unit test for this bug?
Let me work on it