Question

In the breadth first traversal procedure BFS, each vertex v has an attribute v.color. Modify BFS so that instead of x.color, each vertex x has a Boolean attribute called x.mark, whose value is either TRUE or FALSE. The attribute x.mark must be FALSE if x has never been visited. It must be TRUE if x has been visited, but will not be visited again.

BFS(G, s) 1 for each vertex u e G.V-(s 11, color WHITE 4 5 s.color= GRAY 6 s.d=0 7 s.π= NIL 9 ENQUEUE(Q, s) 10 while Q 11 u=DEQUEUE(0) 12 for each v e G.Adj[u] 13 14 15 16 17 18 If V. color WHITE v. color = GRAY ENQUEUE(Q,v) u,color = BLACK

Thank you!!!

Answer 1

Initialise the mark of every vertex as false

First push source in queue and before pushing source in queue make its mark True

similarly when inside check if a vertex have mark False or not if yes push it in queue and change its mark to True

BFS(G,s)

for each vertex u $\epsilon$G.V-{s}

u.mark=False

u.d=inf

u.$\pi$=NIL

s.mark=True

s.d=0

s.$\pi$=NIL

Q=$\phi$

ENQUEUE(Q,s)

while Q$\neq \phi$

u=DEQUEUE(Q)

for each v $\epsilon$ G.adj[u]

if v.mark==False

v.mark=True

v.d=u.d+1

v.$\pi$=NIL

ENQUEUE(Q,v)

If you have any doubt ask in comment Section.Please do upvote the answer