ANONYMOUS wrote:
> and also if anyone can explain the need for
> "if dist[u] is not None:"
> but BFS doesn't need it
> in Dijkstra's, I've rewatched that section explanation a few times but couldn't really understand why.
`if dist[u] is not None` is checking whether the vertex has been marked as visited. An unvisited vertex will have a distance of `None`, while a visited vertex will have some numeric distance.
This is explicitly discussed both in lecture 14 and in the lecture where we covered BFS, but it is a significant enough observation to be worth restating. This is important in the understanding of BFS, rather than just being able to reproduce it on demand:
All incremental tree construction algorithms work by selecting an edge to add to the tree to grow it by one vertex. They differ only in how they select that edge.
In general, there may be multiple edges by which we could add a vertex to the tree, and so when we have chosen one, we must then avoid adding that vertex to the tree again in future. Theoretically we could delete all the other edges to that vertex from the set of options, but the easiest way to do that is to actually just leave them, but whenever an edge to an already visited vertex is picked out, immediately discard it and move on.
For BFS in particular, since we know that the first edge to some vertex we push into the set (queue) will be the first one to come out (FIFO), and hence the one we use to add that vertex, we can instead mark the vertex as visited as soon as we push that first edge, so as to avoid pushing any others in future. Critically, this property only works if we can assume that the edge we just pushed will be the one we use to add that vertex.
The same is not true for DFS or for Dijkstra's or any other incremental tree construction algorithm, since a FIFO queue (and hence BFS) is the only selection strategy where this property holds.
You could implement BFS the same way as we do DFS/Dijkstras/etc., and not mark something as visited until it comes out of the queue, but this will simply result in you pushing a bunch of edges that you are guaranteed to then throw away anyway.
Remember, there are really three states vertices can be in:
- Unseen (there is no edge by which it could be added to the tree)
- Seen (not yet added to the tree, but there is an edge by which it could be)
- Visited (has been added to the tree)
In typical implementations of BFS, we know that the first Seen edge will also be the one that makes it Visited, so Seen is effectively equivalent to Visited, and we can mark a vertex as Visited as soon as we see it. So we effectively only have two states we care about: Unseen and Seen/Visited.
In typical implementations of DFS/Dijkstras/etc., we cannot mark a vertex as Visited as soon as we see it, because we might find another edge later which is how it will be added to the tree. Indeed, we cannot start ignoring edges to the vertex until it has come of the stack/priority queue and has actually been visited, so for these algorithms the Seen state is effectively the same as the Unseen state, and so we only have two states we care about: Unseen/Seen and Visited.
So in this particular case, we know that `dist[u] is None` if `u` is Unseen/Seen and `dist[u] is not None` if `u` is Visited.
