Depth First Search (DFS) is a fundamental graph traversal algorithm widely used in Artificial Intelligence and Machine Learning laboratories for exploring state spaces, searching solution paths, and analyzing graph structures. It follows the principle of exploring as far as possible along each branch before backtracking. In AI applications such as problem solving, puzzle solving, path finding, and tree-based model exploration, DFS provides a systematic way to traverse nodes either recursively or using an explicit stack data structure. In Python, DFS can be implemented efficiently using an adjacency list representation of a graph. An adjacency list stores each vertex and a list of its neighboring vertices. This representation is memory-efficient and suitable for sparse graphs, which are common in real-world AI problems. There are two main approaches to implementing DFS in Python: recursive implementation and iterative implementation using a stack. The recursive approach is simpler and leverages the system call stack, while the iterative approach uses an explicit stack data structure and provides more control over traversal. Below is a Python program that implements Depth First Search using recursion: ```python # Depth First Search using recursion def dfs_recursive(graph, node, visited): if node not in visited: print(node, end=" ") visited.add(node) for neighbor in graph[node]: dfs_recursive(graph, neighbor, visited) # Example graph represented as adjacency list graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': [] } visited = set() print("DFS Traversal (Recursive):") dfs_recursive(graph, 'A', visited) ``` In this program, the graph is represented as a dictionary where each key represents a