Depth First Search (DFS)

Depth First Search (DFS). Graph Traversal Algorithm.

Graphs in Computer Science. A graph is a non-linear data structure consisting of nodes (vertices) and edges Vertices represent entities, edges represent relationships Graphs can be: Directed (edges have direction) Undirected (no direction) Used in: Social networks Maps & navigation Dependency systems Represented as: G = (V, E).

Introduction to Depth First Search. [image] DFS Source Node Output: O, 1. 4. 5, 2. 6, 3, 7.

DFS Traversal Example. Consider a graph with nodes: A, B, C, D Edges: A–B, B–D, A–C Starting from node A, DFS traversal is: A → B → D → C DFS explores one path completely before moving to another.

DFS and the Stack Data Structure. DFS uses a Stack (LIFO – Last In, First Out) The most recently visited node is explored first Helps in backtracking when no unvisited nodes remain DFS can be implemented using: Stack (iterative method) Recursion.

[image] unmark au t be Ct•xose any unmark Mark •E Stop do-ot it z R G throuö R.

DFS Pseudocode. [image]. DFS can be written using a recursive approach It follows the idea of visiting a node and exploring its neighbors A visited array ensures nodes are not revisited DFS(v): mark v as visited for each neighbor u: if u is not visited: DFS(u).

Complete DFS Code Structure. Code: #include <vector> using namespace std; vector<int> adj[100]; bool visited[100]; void DFS(int v).

Time and Space Complexity of DFS. Time Complexity: O(V + E) Space Complexity: O(V) Efficient for traversing large graphs Visits each vertex and edge only once.

Applications of Depth First Search. Maze solving and path finding Cycle detection in graphs Web crawling and search engines Game AI and decision making Topological sorting in directed graphs Finding connected components in a graph Detecting strongly connected components Solving puzzles like sudoku and backtracking.