Rewrite the Pseudo-code of Breadth-First-Search, which were given in the slides,

Question

Rewrite the Pseudo-code of Breadth-First-Search, which were given in the slides, such that it returns the edge-distance (number of edges between two vertex) for each vertex from the source vertex s as well as the shortest path to reach every vertex from source s.

No code required; only explanation/pseudo code.

---------------------------------------------------------------------

Pseudo Code

mark starting vertex as visited; put on queue

while the queue is not empty

{

dequeue the next node

for all unvisited vertices adjacent to this one

{

mark vertex as visited

add vertex to queue

}

}

Explanation / Answer

create an array of size n and initialize it to 0(n is the number of vertices where array[i] is the distnce from source to ith vertex)

mark source as s.

make array[s]=0 //as distance from source to source is always 0

eneque(s)

while(queue is not empty)

{

deque the next node and mark it as head

for all node "V" connected to head and unvisted

{

mark V as visited

eneque(V)

array[V]=array[head]+1

}

}

So the array will store the distance of each vertex from the source.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.