Depth-First Search
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Imagine navigating a maze: you pick a path and follow it until you hit a dead end, then you backtrack to the last intersection and try a different path. DFS operates similarly on graphs.
Consider a social network where users are nodes and friendships are edges. You can use DFS to find all users reachable from a specific starting user. Starting at that user, you explore their friends, then their friends' friends, and so on, until you've exhausted all reachable users along each friendship chain. This could be used to identify communities or analyze the spread of information.DFS can be implemented recursively or iteratively using a stack. The algorithm typically marks visited nodes to avoid cycles. Its time complexity is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph, assuming the graph is represented using an adjacency list. If an adjacency matrix is used, the time complexity is O(V^2). DFS is useful for tasks like topological sorting, cycle detection, and finding connected components in a graph.