retagged by
1,224 views
2 votes
2 votes

In the qusetion he meant that it can be implemented using two colors by eliminating the Grey color... i think there must be one more check such that if v.pi ==nil if it must be done by two colors...only by eliminating lines 5 and 14 we cannot get the same results or am i wrong?

As because through BFS we place the vertices in queue which are accessible from the source...but if we donot mark them grey then when the elements in the queue can have edges and this can result in insertion of same vertex twice by updating the parent and distance again which was updated initial by source vertex

retagged by

1 Answer

0 votes
0 votes
In BFS, we take a vertex from the queue, processes all its neighbours and put them in the queue if unprocessed yet.

In the given code lines 12-17 happen for each vertex taken from the queue and before the next vertex is taken, line 18 happens which makes the color of the current vertex "BLACK". Now, due to line no. 13, this vertex will never be taken again due to any edge coming back. (This may not be the case if we were using DFS). So, even if lines 5 and 14 are remved thw algorithm works fine. We also do not need to see if parent is null to avoid a cycle.

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
2
gautamcse27 asked Sep 3, 2016
1,211 views
What is the running time of BFS if we represent its input graph by an adjacency matrix and modify the algorithm to handle this form of input?