Hi Vaidehi, thanks for your article. I like this series of yours and I feel it's a useful instrument to learn/review algorithm.
I just have the feeling that the "backbone" section is slightly misleading. I understand it's just a high level description but I think there is an issue and if you try to implement it in code based on this description, it will result in an error.
The issue in my opinion is with steps 3 and 4:
3. If that node has any neighbors, check to see if they have been “visited” or not.
4. Add any neighboring nodes that still need to be “visited” to the queue.
If you try to apply this logic to a 4 vertexes graph, corresponding to the geometrical figure of a square, you will end up with the last vertex will be added twice to the list of vertexes to visit .
Because we are in BFS, so at the time we are exploring the 1th level, the last vertex in our square it's not been visited yet. And it won't be until we switch to the 2nd level.
So, according to those steps 3 and 4, we end up adding the last node a second time.
The issue is not present in the guided example, where you expand the logic of this algorithm.
What do you think?
thanks again
paolo
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Hi Vaidehi, thanks for your article. I like this series of yours and I feel it's a useful instrument to learn/review algorithm.
I just have the feeling that the "backbone" section is slightly misleading. I understand it's just a high level description but I think there is an issue and if you try to implement it in code based on this description, it will result in an error.
The issue in my opinion is with steps 3 and 4:
If you try to apply this logic to a 4 vertexes graph, corresponding to the geometrical figure of a square, you will end up with the last vertex will be added twice to the list of vertexes to visit .
Because we are in BFS, so at the time we are exploring the 1th level, the last vertex in our square it's not been visited yet. And it won't be until we switch to the 2nd level.
So, according to those steps 3 and 4, we end up adding the last node a second time.
The issue is not present in the guided example, where you expand the logic of this algorithm.
What do you think?
thanks again
paolo