Depth-First Search (DFS)
An approach for traversing trees and graph-like data structures is called depth-first search. Usually, it begins by investigating the frontier's deepest node. The procedure begins at the root node and works its way down the search tree to the lowest level, reaching nodes that have no successors.
To aid in graph backtracking, more memory—typically in the form of a stack—is required to record the nodes that have been found thus far along a given branch.
The 19th-century French mathematician Charles Pierre studied a variation of depth-first search as a maze-solving technique.
Example of Depth-First Search
Output -- A B S C D E H G F
The following is the step-by-step procedure for implementing the DFS traversal:
1. To begin, arrange all of the graph's vertices into a stack.
2. Select any vertex to serve as the traversal's starting point and add it to the stack.
3. Next, move a vertex that isn't visited to the top of the stack by pushing it next to the vertex at the top.
4. Continue doing this until there are no more vertices to visit from the top vertex of the stack.
5. Return and remove a vertex from the stack if there are none left.
6. Until the stack is empty, keep repeating steps 2, 3, and 4.
Algorithm of Depth First Search (DFS) in AI
Step 1: For every node in Graph (G), set STATUS = 1 (ready status).
Step 2: Place the initial node A on the stack and designate it as in the waiting state (THE STATE = 2).
Step 3: Until STACK is empty, repeat Steps 4 and 5.
Step 4: Remove node N at the top. After processing it, set its processed state's State to 3.
Step 5: Place all of N's neighbors who are in the ready state (whose State = 1) on the stack and set their THE STATE = 2 (waiting for state). [LOOP END].
Step 6: Go Out.
Applications of Depth-First Search (DFS) in AI
1. Topological sorting, scheduling issues, cycle identification in graphs, and solving single-solution puzzles like sudoku or mazes all employ depth-first search.
2. Other uses include network analysis, such as determining whether a graph is separated. A common subroutine in network flow algorithms, like the Ford-Fulkerson algorithm, is depth-first search.
3. In graph theory matching algorithms like the Hopcroft-Karp algorithm, DFS is also employed as a subroutine.
4. Routing, identifying spanning trees, and mapping routes all require depth-first searches.
Time Complexity of DFS Algorithm
Explicit Time Complexity:
In the worst-case situation, DFS visits every vertex and edge exactly once, which results in this time complexity. This complexity is for a repeat-free, explicit traversal of the DFS. O(|V| + |E|) is a typical representation of the time complexity of DFS.
Whereas The numbers V and E stand for the number of vertices and edges, respectively.
Implicit Time Complexity:
Rather than measuring time complexity in terms of the number of edges and vertices in a graph, implicit time complexity is acceptable when analyzing the number of nodes visited in the tree.
The implicit traversing of DFS can be expressed as O(bd) in this way:
The branching factor is represented by b, and the search depth is represented by d.
Space complexity of DFS:
O(|V|) is a typical representation for the space complexity of DFS.
Whereas The symbol V stands for the number of vertices. This is due to the fact that DFS generally tracks visited vertices using extra data structures like stack or recursion stack.
