search

davecom / SwiftGraph

A Graph Data Structure in Pure Swift
Apache License 2.0
758 stars 80 forks source link

Improve dfs performance #51

Closed ferranpujolcamins closed 6 years ago

davecom commented 6 years ago

Interesting; I'm surprised moving the visited[] set has a significant impact on performance. Are we sure this won't lead to duplicate traversals in some edges cases?

ferranpujolcamins commented 6 years ago

I can't think of any. Plus the bfs code is already like this. With this change we avoid pushing a vertex to the stack only to later realize that we had already pushed it before.

davecom commented 6 years ago

Cool, thanks for the explanation and great contribution!