Depth first search of graph is a graph traversal algorithm that starts at a root vertex and explores as far as possible along each branch before backtracking. This algorithm is commonly used to traverse or search a graph and can be implemented using recursion or a stack data structure.
The time complexity of depth first search of graph is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This means that the time required to traverse the entire graph is directly proportional to the number of vertices and edges in the graph.
Depth first search of graph differs from breadth first search in the order in which vertices are visited. In depth first search, all the descendants of a vertex are explored first before moving on to the next vertex. In contrast, breadth first search explores all the vertices at the current depth before moving on to the next depth.
A visited array is used in depth first search of graph to keep track of which vertices have already been visited. This prevents the algorithm from getting stuck in an infinite loop by visiting the same vertex multiple times. The array is typically initialized to all false and is updated to true once a vertex has been visited.
Depth first search of graph has many applications in computer science, including topological sorting, cycle detection, path finding, and maze generation. It is also commonly used in artificial intelligence, web crawling, and social network analysis.