Repository navigation
Possible bug in Prim's algorithm #85
Description
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.
Activity
gokberksahin commentedon May 5, 2018
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 commentedon May 11, 2018
I'll gladly fix this in master branch if you can provide a unit test which shows the bug.
phishman3579 commentedon Feb 21, 2019
Has anyone come up with a good unit test for this bug?
KannanSnair commentedon Jan 23, 2020
Let me work on it