For the following graphs a and b give the order that the nod

For the following graphs (a) and (b), give the order that the nodes will be visited when doing a BFS starting at the node 1; give the order that the nodes will be visited when doing a DFS starting at the node 1.

Solution

BFS Rules:
1.Start with a node.
2.Visit its adjacent unvisited vertex (then mark itto visited).
3.Insert in the queue.
4.If no adjacent vertex is found, remove the first vertexfrom the queue.
5.Repeat rule 1-3
6.When there are no unvisited nodes remain in the graph stop.

Graph-a):BFS explained:
1.Start with node 1 and mark it visited.
2.Then next unvisited adjacent nodes from 1 are 2,4
3.you can choose any one node from 2,4 but here we choose 2 numerically and mar it visited and enque it.
so node in our queue is: 2
4.Then we choose next unvisted node from 1 and its 4, so we mark it as visited and enqueue it,
queue becomes: 4 2
5.So 1 is left with no unvisited nodes so we dequeue 2
6.From 2 there is only 0ne node 7 is unvisited so we mark it as visited and enqueue
so queue becomes:7 4
7.now there are no unvisited nodes from 2 so we dequeue 4 from the queue.
8.so from4 we have 3 and 5 unvisited nodes.
9.so mark 3 as visited and enque it then mark 5 as visited and enque it.
que: 5 3 7
10.so there are no unvisited nodes from 4.
11.now dequeue 7 from queue but there are no unvisitednodes from 7 so dequeue next node which is 3.
12.from 3 there is 6 which is unvisited so mark it as visited and enqueue it.
queue:6 5
13.Stop.

Ans: BFS for graph a---->>> 1-2-4-7-3-5-6
BFS for graph b---->>>1-2-3-4-7-6-5

DFS Rules:
1.Start with a node.
2.Visit its adjacent unvisited vertex (then mark itto visited).
3.Push it into the stack
4.If no adjacent vertex is found, pop the first vertex from the stack.
5.Repeat rule 1-3
6.When there are no unvisited nodes remain in the graph stop.

Graph a)DFS explained:
1.Start with node 1. mark it visited and push it into the stack.
stack: 1
2.from 1 we have two nodes unvisited i.e.2,4
3.choose 2 numerically for simplicity, you can choose 4 also. and push 2 onto the stack.
stack: 2
   1
4.Next unvisited node from 2 is 7 mark 7 as visited and push it onto the stack
stack: 7
   2
   1
5.From 7 we have we have 3 and 5 as unvisited node.choose 3 and push itonto the stack.
6.from 3 we have 4 and 6 as unvisited nodes.choose 4 and push onto the stack.
7.from 4 we have 5 as unvisited node.so choose 5 and mark it visited and push onto the stack.
8.from 5 we have 6 as unvisited node.So mark it visited and push onto the stack
8.Stop.

Ans:DFS for graph a)1-2-7-3-4-5-6
DFS for graph b)1-2-3-4-7-6-5