-
Notifications
You must be signed in to change notification settings - Fork 1.8k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Possible bug in Prim's algorithm #85
Comments
Yeah i encountered same issue, added these lines for possibility of a cycle.
|
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.
The text was updated successfully, but these errors were encountered: