Lesson DFS BFS Algorithms - Artificial Intelligence - ثالث ثانوي

Lesson 2 DFS/BFS Algorithms Link to digital lesson www.ien.edu.sa Searching in Graphs There are cases in which you need to find a specific node in a graph (e.g. a person searching for the city they want to travel to) or visit every node in a graph to perform a certain operation (e.g. printing the graph nodes). In order to achieve this, you need to visit every node in the graph until you find the one you need. This procedure is called graph search or graph traversal, and there are many search algorithms that help implement it, including: • Breadth-first search (BFS) algorithm • Depth-first search (DFS) algorithm Broadcasting node Other nodes Broadcasting node's neighbors BFS example: Network broadcasting Breadth-first search (BFS) algorithm The Breadth-first search (BFS) explores the graph level by level. You start from a root node (start node), then you visit the nodes that are directly connected with it, one by one. When all the nodes of the level have been visited, you move on to the next level following the same procedure, as shown in figure 2.6. To keep track of the nodes you have visited, you use a queue. When a node is explored, you enqueue its child. Then, you dequeue the next node to be explored. وزارة التعليم Ministry of Education 2024-1446 DFS example: Maze solving Level 0 A 1 2 Level 1 B C 3 Level 2 D E 4 5 FL Figure 2.6: BFS Algorithm G 6 79

The following example shows how the BFS algorithm works. Using the following diagram, determine which nodes to visit to get from root node A to node F. (note: use the appropriate data structure) A B C D E F 0 1 2 Graph Queue You must traverse all the nodes in layer 1 before you move on to the nodes in layer 2 1 Starting from the root node (node A). Add the root node to the queue. 2 Remove the root node from the queue and process it. Next, add the children of this node to the queue (nodes B and C). 3 Remove the node at the front of the queue (node B) from the queue and process it. Next, add the children of this node to the queue (nodes D and E). A B C A Visited B C A B C D E F D E F D E وزارة التعليم Ministry of Education 80 2024-1446 A 0 A B C 0 1 <-- B C 0 A B C C D E 0 1 2 0 1 2 FL

4 Remove node C and process it, then add its children. A 5 Remove node D and process it (it has no children). A 6 Remove node E and process it (it has no children). A B C B D E F D E C FL B C D E C <-- D E D <-- EF <--- E F 0 1 0 1 0 D E LL 0 1 2 7 Remove node F and process it. The queue is now empty and the search is terminated. A B C The nodes visited using the BFS algorithm are: A, B, C, D, E, F D E F Let's see how you can implement the BFS algorithm in Python. graph = { "A" ["B", "C"], "B" ["D", "E"], "C" : ["F"], "D" : [], "E" : [], "F" : [] } visitedBFS = [ ] # List to keep track of visited nodes queue = [ ] #Initialize a queue · #bfs function · def bfs(visited, graph, node): visited.append(node) وزارة التعليم Ministry of Education 2024-1446 LL FL 81

queue.append(node) while queue: n = queue.pop(0) print (n, end = " ") for neighbor in graph[n]: if neighbor not in visited: visited.append(neighbor) queue.append(neighbor) #main program bfs (visited BFS, graph, "A") A B C D E F Practical Applications of the BFS Algorithm BFS is used by peer-to-peer networks to find all neighbor nodes in order to establish communication. وزارة التعليم Ministry of Education 82 2024-1446 Social media use BFS to connect nodes of users that are related, such as those with similar interests or a common location. GPS navigation systems use BFS to find neighboring places so they can create routes for the user. To achieve network broadcasting of some packets, BFS is used. INFORMATION The BFS algorithm can be developed by defining the starting point (Initial State) and the target point (Goal State) to determine the path between them.

Depth-first search (DFS) algorithm In Depth-first search (DFS), you keep following the edges, going deeper and deeper into the graph. DFS uses a recursive procedure to traverse through the nodes. When you reach a node that has no edges to any new node, you go back to the previous node and continue the process. The DFS algorithm uses a stack data structure to keep track of the exploration trail. When a node is explored, it is pushed into the stack. When you need to go back, you pop the node from the stack as illustrated in figure 2.7. The following example shows how the Depth-first search (DFS) algorithm works. Using the following diagram, trace the order of traversal followed by the DFS algorithm (note: use appropriate data structure). Level 0 A 1 Level 1 B C 2 3 4 5 6 Level 2 D E F G Figure 2.7: DFS Algorithm 1 Process root A and add it to the stack. A B C A B C D E F Graph Stack D E F A 2 Process node B and add it to the stack. A Visited 3 Process node D and add it to the stack. A visited node that has no children is removed from the stack (remove node D). B C D E FL B A 4 Process node E and add it to the stack. A visited node that has no children is removed from the stack (remove node E). برة التعليم Ministry of Education 2024-1446 A E E B C B B E FL A A A D D B C B B E F A A HISTORY The first version of the Depth-First Search (DFS) algorithm was developed in the 19th century by a French mathematician as a strategy for solving mazes. 83

5 Remove node B. B A C B <--- D E F A 6 Process node C and add it to the stack. A C B C C D E F A A 7 Process node F and add it to the stack. 8 The stack is empty and the DFS accordingly terminates. B A D E C FL பட F A B C C C A A D E FL F C C ←- A A A Let's see how you can implement the Depth-first search (DFS) algorithm in Python. graph = { "A" : ["B","C"], The nodes visited using the DFS algorithm are: A, B, D, E, C, F "B" : ["D","E"], "C" : ["F"], "D" : [], "E" : [], "F" : [] } visited DFS = = # dfs function [ ] # list to keep track of visited nodes def dfs(visited, graph, node): if node not in visited: print(node, end = " ") visited.append(node) for neighbor in graph[node]: dfs(visited, graph, neighbor). A stack is used indirectly through the runtime stack for tracking recursive calls. # main program dfs(visited DFS, graph, "A") ABDEC F وزارة التعليم Ministry of Education 84 2024-1446

Practical Applications of the DFS Algorithm DFS algorithm is used in Path finding to explore different paths in depth for maps and roads and find the best path. DFS is used to solve mazes by traversing all possible routes. Cycles in a graph can be detected using DFS by the presence of a back edge that passes through a node twice. Table 2.4: Comparison of the BFS and DFS algorithms Comparison criteria DFS BFS Implementation method Traverses according to tree depth. Traverses according to tree level. Data structure Uses the stack data structure to keep track of the next location to visit. Use Search method Uses queue data structure to keep track of the next location to visit. Better when the structure of the graph is narrow and long. Better when the structure of the graph is wide and short. Goes to the bottom of a subtree, then backtracks. Finds the path to the destination with the least number of edges. First visited nodes Children are visited before siblings. Siblings are visited before children. وزارة التعليم Ministry of Education 2024-1446 85

Exercises 1 Read the sentences and tick ✓ True or False. 1. The BFS and DFS algorithms are implemented with the use of recursion. 2. BFS and DFS cannot be used on tree data structures. 3. The BFS algorithm is implemented with the help of a linked list data structure. 4. The DFS algorithm can be implemented with the help of a stack data structure. 5. The BFS algorithm cannot be used in network broadcasting. 2 Explain how the BFS algorithm and the DFS algorithm work. 3 Compare the differences between the BFS and DFS algorithms. وزارة التعليم Ministry of Education 86 2024-1446 True False

4 In the diagram to the right, you want to go from the start node (A) to the target node (G). Apply BFS and DFS algorithms using the appropriate data structure (stack/queue), indicating which nodes are visited. وزارة التعليم Ministry of Education 2024-1446 B E F A C K L M H J 87

5 Write a Python function that performs BFS on a graph to check if there is a path between two given nodes. 6 Write a Python function that uses DFS to find the shortest path in a graph. وزارة التعليم Ministry of Education 88 2024-1446