Search techniques- BFS and DFS

[Audio] SEARCH TECHNIQUES- BFS AND DFS Objective of lesson Understand BFS and DFS traversing methods used in searching a graph.

[Audio] BREADTH FIRST SEARCH ( BFS) Breadth First Search is the traversing method used in graphs.

[Audio] Example Vertex A is expanded and stored in the queue Vertices B, D and G successors of A, are expanded and stored in the queue meanwhile Vertex A removed Now B at the front end of the queue is removed along with storing its successor vertices E and F Vertex D is at the front end of the queue is removed, and its connected node F is already visited Vertex G is removed from the queue, and it has successor E which is already visited Now E and F are removed from the queue, and its successor vertex C is traversed and stored in the queue At last C is also removed and the queue is empty which means we are done The generated Output is – A, B, D, G, E, F, C.

[Audio] Applications BFS can be useful in finding whether the graph has connected components or not BFS is also better at finding the shortest path in the graph could be seen as a network.

[Audio] DEPTH FIRST SEARCH Depth First Search traversing method uses the stack for storing the visited vertices.

[Audio] EXAMPLE Considering A as the starting vertex which is explored and stored in the stack B successor vertex of A is stored in the stack Vertex B have two successors E and F, among them alphabetically E is explored first and stored in the stack The successor of vertex E, i.e., G is stored in the stack Vertex G have two connected vertices, and both are already visited, so G is popped out from the stack Similarly, E s also removed Now, vertex B is at the top of the stack, its another node F is explored and stored in the stack Vertex F has two successor C and D, between them C is traversed first and stored in the stack Vertex C only have one predecessor which is already visited, so it is removed from the stack Now vertex D connected to F is visited and stored in the stack As vertex D doesn't have any unvisited nodes, therefore D is removed Similarly, F, B and A are also popped The generated output is – A, B, E, G, F, C, D.

[Audio] Application A graph is called two edges connected if and only if it remains connected even if one of its edges is removed. This application is very useful, in computer networks where the failure of one link in the network will not affect the remaining network, and it would be still connected..

[Audio] KEY DIFFERENCES BETWEEN BFS AND DFS Queue data structure is used in BFS Memory space is efficiently utilized in DFS while space utilization in BFS is not effective DFS constructs narrow and long trees.