DFS of a directed graph is a depth-wise traversal technique that follows edge directions. Learn DFS algorithm, pseudocode, example, complexity, and applications like SCC and topological sorting.
DFS of a Directed Graph:
Introduction
A Directed Graph (Digraph) is a graph in which each edge has a direction.
Depth First Search (DFS) is a graph traversal algorithm used to visit vertices of a directed graph in a depth-wise manner.
Starting from a given source vertex, DFS explores as deep as possible along outgoing edges, and then visits remaining vertices using backtracking.
Why Use DFS in a Directed Graph?
- Determine reachability (which vertices can be reached from a given vertex)
- Perform cycle detection
- Find Strongly Connected Components (SCCs)
- Support topological sorting
Data Structures Used in DFS
DFS uses:
- Stack, or
- Recursion (Call Stack)
A visited array is used to avoid revisiting vertices.
Working Method of DFS in a Directed Graph
- Mark the starting vertex as visited
- Traverse to its unvisited adjacent vertex following the direction of edges
- Continue this process until no further unvisited vertex is available
- Backtrack and continue DFS for remaining unvisited vertices
Algorithm: DFS of a Directed Graph
DFS_Directed(G)
mark all vertices as unvisited
for each vertex v in G
if v is not visited
DFS_Visit(v)
DFS_Visit(v)
mark v as visited
for each vertex u such that there is an edge v → u
if u is not visited
DFS_Visit(u)
Example
Consider the following directed graph:
A → B → C
↑ ↓
E ← D
If DFS starts from vertex A, one possible traversal order is:
A→B→C→D→E
(Note: The traversal order depends on the adjacency list representation.)
Features of DFS in Directed Graph
- Traversal follows the direction of edges
- Each vertex is visited only once
- Uses backtracking
- Useful for discovering graph structure
Time and Space Complexity
- Time Complexity: O(V+E)
- Space Complexity: O(V)
Where:
- V = number of vertices
- E = number of directed edges
Applications of DFS in Directed Graph
- Cycle detection in directed graphs
- Finding Strongly Connected Components (SCC)
- Topological sorting
- Program dependency analysis
- Deadlock detection
Conclusion
DFS of a directed graph is an efficient graph traversal technique that explores vertices depth-wise while respecting edge direction.
It plays a key role in solving important problems such as cycle detection, SCC identification, and topological sorting.
Some More:
- POP- Introduction to Programming Using ‘C’
- DS – Data structure Using C
- OOP – Object Oriented Programming
- Java Programming
- DBMS – Database Management System
- RDBMS – Relational Database Management System
- https://defineinfoloop.blogspot.com/?m=1