Overview
The depth-first algorithm is attributed to Charles Pierre Tremaux, a 19th century French mathematician.
Concept
Depth-first search is an algorithm for traversing a tree or graph data structure by starting at the root and continuing as far as possible along a branch before back tracking.
Algorithmic Complexity
Big-O
Algorithm | Data Structure | Time Complexity - Average | Time Complexity - Worst | Space Complexity - Worst |
---|---|---|---|---|
Depth First Search | Graph of |V| vertices and |E| edges | - | O(|E|+|V|) | O(|V|) |
Implementation
Java Implementation
Coming soon!
References
Wikipedia: Depth-first search