Depth First Search Algorithm
Reviewing what I studied, how this work will be explained as well.
Depth First Search
DFS explores as far as possible along each branch before backtracking. Unlike BFS which explores level by level, DFS dives deep into the graph, prioritizing depth over breadth.
DFS first visits a node, then recursively visits all nodes adjacent to the recently visited nodes that haven’t been visited yet. This creates a pattern where we explore as deep as possible along one path before backtracking.
It is typically implemented using either recursion or a stack. In the recursive implementation, we visit a node, mark it as visited, and then recursively call the DFS function on each unvisited adjacent node. In the stack-based implementation, we start with the initial node in the stack, then repeatedly pop a node, process it, and push all its unvisited adjacent nodes onto the stack. This process continues until the stack is empty.
DFS is equivalent to Pre-order Traversal (Node -> Left -> Right) in trees when implemented recursively, though the exact traversal order depends on how adjacent nodes are processed. Which obviously you can choose the other Traversal Order. (In-order, postorder)
Implementation
- Recursive
struct Vertex
{
Vertex(int v) { value = v; }
int value = -1;
bool visited = false;
vector<Vertex*> out_neighbors;
}
void DepthFirstPathHelper(Vertex* source, Vertex* dest, vector<Vertex*> path) {
path.push_back(source);
if (source == dest) { cout << "Path Found" << endl; }
else {
source->visited = true;
for (auto* e : source->out_neighbors) {
if(!e->visited) DepthFirstPathHelper(e, dest, path);
// backtracking
source->visited = false;
}
}
}
void DFS(int source, int dest) {
for (auto*v : vertices) {
v->visited = false;
}
DepthFirstPathHelper(vertices[source], vertices[dest], vector<Vertex*>())
}
- Stack
template <typename T>
auto DFS(const Graph<T>& G, unsigned start) {
stack<unsigned> stack;
stack<unsigned> visited;
vector<unsigned> visit_order;
stack.push(start);
while(!stack.empty()) {
auto currentVertex = stack.top();
stack.pop();
if(visited.find(current_vertex) == visited.end()) {
visited.insert(current_vertex);
visit_order.push_back(current_vertex);
for (auto& e : G.edges(currentVertex)) {
if(visited.find(e.dst) == visited.end()) {
stack.push(e.dst);
}
}
}
}
return visit_order;
}
Time Complexity
It is similar fashion as BFS. But if adjacent link list are used, it is possible to say O(m), in general, you can say O (V + E)
