Question

For the following graph, give the result of any one breadth-first traversal beginning at D, where the label of a vertex is printed when the vertex is visited. D E A B с F G

Answer 1

Breadth First traversal(BFT) approach:- Visiting the Node Breadth wise not depth wise.
Whatever node encounter first visit all the node directly connected to the node and
then proceed for down to the graph/tree.

In the given graph Breadth-first traversal beginning at D.
Print D and tag D as visited.
Now visit all the node which is not visited and directly connected with D.
First Visit A, Print A, Tag A as visited and push A into the Queue.
Queue:- A
First Visit E, Print E, Tag E as visited and push E into the Queue.
Queue:- A , E
All node directly connected with D is visited then we pop out one element from Queue
A is pop out and visit all node that is directly connected with A.
Only B is directly connected to A.
Then Visit B, Print B, Tag B as visited and push B into the Queue.
Queue:- E , B
Again pop one element from queue. E is popped and only B is directly connected
and already visited.
Queue:- B
Now pop B, and visit its directly connected nodes.
First Visit F, Print F, Tag F as visited and push F into the Queue.
Queue:- F
Now Visit G, Print G ,Tag G as visited and push G into the Queue.
Queue:- F , G
Now Visit C, Print C Tag C as visited and push C into the Queue.
Queue:- F , G , C
Now pop F,G,C because all the node has traversed.

Breadth-first Traversal:-
D --> A --> E --> B --> F--> G --> C