We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Thanks, this definitely helped. You actually don't need a set of seen vertices though. If distances[node] == -1, it hasn't been seen yet, and thanks to BFS you'll always visit a node at the earliest possible time. It's still an O(1) check and you save O(n) space.
BFS: Shortest Reach in a Graph
You are viewing a single comment's thread. Return to all comments →
Thanks, this definitely helped. You actually don't need a set of seen vertices though. If distances[node] == -1, it hasn't been seen yet, and thanks to BFS you'll always visit a node at the earliest possible time. It's still an O(1) check and you save O(n) space.