Skip to main content

Depth First Traversal for a Graph

Depth First Traversal (DFT) is a graph traversal algorithm that explores a graph by visiting vertices (nodes) in a depth-first manner. In other words, it visits a vertex and then recursively visits all its adjacent vertices before backtracking.

To perform DFT, we start at a given vertex and mark it as visited. Then, we recursively visit all the unvisited adjacent vertices. We continue this process until all the vertices have been visited.

DFT can be implemented using either recursion or a stack. The recursive approach is easier to implement and understand, but it may not be suitable for large graphs due to the stack size limitation. The iterative approach using a stack is more efficient and can handle large graphs.

DFT is used for various applications, such as searching a graph for a specific vertex, finding a path between two vertices, detecting cycles in a graph, and determining the connectivity of a graph.

DFS (Depth First Search) traversals are possible in adjacency matrix and adjacency list. Here given implemented solution of adjacency list.

DFS Directed Graph
DFS :  4  2  1  3  0  5

Here given code implementation process.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment