java-algorithms-implementation
java-algorithms-implementation copied to clipboard
phishman3579
Possible bug in Prim's algorithm
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.
