Depth-First Search (DFS) in Graph
Welcome to our beginner's guide to Depth-First Search (DFS) in Graph Theory! DFS is another fundamental algorithm used to traverse or search through the nodes of a graph in a systematic manner. Let's explore this fascinating algorithm together!
What is Depth-First Search (DFS)?
Depth-First Search is an algorithm used to traverse or search through the nodes of a graph in a depthward motion. It starts at a specific node (often referred to as the "source" node) and explores as far as possible along each branch before backtracking.
Imagine you're exploring a maze again. DFS would explore as far as possible along one path before backtracking and exploring another path.
How does DFS Work?
DFS employs a simple strategy of exploring nodes as deeply as possible along each branch before backtracking. The algorithm proceeds as follows:
- Start with the source node and mark it as visited.
- Explore one of the unvisited neighbors of the source node.
- If an unvisited neighbor is found, recursively apply steps 1 and 2 to it.
- If no unvisited neighbors are found, backtrack to the previous node and repeat step 2.
- Repeat steps 1-4 until all reachable nodes are visited.
Exploring Depth-First Search (DFS) with an Example
Depth-First Search (DFS) is a fundamental graph traversal technique. We'll demonstrate it using a simple graph structure:
A
/ \
B - C
/ \ \
D - E - F
In this graph, we have the following connections:
- A is linked to B and C.
- B is linked to A, D, and E.
- C is linked to A and F.
- D is linked to B and E.
- E is linked to B, D, and F.
- F is linked to C and E.
We begin our DFS traversal from node A.
DFS Traversal Steps:
Note:When we call something recursively, it uses the stack for execution and backtracking.
- Initiate at Node A (Starting Point):
- Mark A as visited.
- Visited: [A],Recursion Stack: [A]
- Explore unvisited adjacent nodes:
- Move to B, mark as visited.
- Visited: [A, B], Stack: [A, B]
- Continue exploring adjacent nodes:
- Proceed to D, mark as visited.
- Visited: [A, B, D], Stack: [A, B, D]
- Explore further adjacent nodes:
- Visit E, mark as visited.
- Visited: [A, B, D, E], Stack: [A, B, D, E]
- Continue exploration:
- Go to F, mark as visited.
- Visited: [A, B, D, E, F], Stack: [A, B, D, E, F]
- Visit C, mark as visited.
- Visited: [A, B, D, E, F, C], Stack: [A, B, D, E, F, C]
A
/ \
B - C
/ \ \
D - E - F
A
/ \
B - C
/ \ \
D - E - F
A
/ \
B - C
/ \ \
D - E - F
A
/ \
B - C
/ \ \
D - E - F
A
/ \
B - C
/ \ \
D - E - F
A
/ \
B - C
/ \ \
D - E - F
And at the end Stack: [A, B, D, E, F, C] get backtracked from recurssion.
Output: Nodes visited in DFS order: A, B, D, E, F, C
Time Complexity:
The time complexity of DFS is O(V + E), where V represents the number of vertices and E the number of edges in the graph.
Space Complexity:
The space complexity of DFS, in the worst-case scenario, is O(V), considering V as the number of vertices.
Implementing DFS in Code
Now, let's take a look at how we can implement Depth-First Search in code. We'll provide examples in several programming languages to help you get started:
package codeKatha;
import java.util.*;
public class DFS {
public void depthFirstSearch(Graph graph, Node source) {
Set<Node> visited = new HashSet<>();
dfsHelper(source, visited, graph);
}
private void dfsHelper(Node node, Set<Node> visited, Graph graph) {
visited.add(node);
System.out.println(node);
for (Node neighbor : graph.getNeighbors(node)) {
if (!visited.contains(neighbor)) {
dfsHelper(neighbor, visited, graph);
}
}
}
}
#include <iostream>
#include <unordered_set>
#include "Graph.h"
void DFS(Node& node, std::unordered_set<Node>& visited, Graph& graph) {
visited.insert(node);
std::cout << node << std::endl;
for (Node neighbor : graph.getNeighbors(node)) {
if (visited.find(neighbor) == visited.end()) {
DFS(neighbor, visited, graph);
}
}
}
class DFS:
def depth_first_search(self, graph, node, visited):
visited.add(node)
print(node)
for neighbor in graph.get_neighbors(node):
if neighbor not in visited:
self.depth_first_search(graph, neighbor, visited)
class DFS {
depthFirstSearch(node, visited, graph) {
visited.add(node);
console.log(node);
for (let neighbor of graph.getNeighbors(node)) {
if (!visited.has(neighbor)) {
this.depthFirstSearch(neighbor, visited, graph);
}
}
}
}
Graph: Concept and Important Algorithms
1. Basics of Graph Data Structure2. Breadth-First Search (BFS) in Graph
3. Depth-First Search (DFS) in Graph
4. Topological Sort in Graph
5. Union-Find Algorithm in Graph
6. Prim's Algorithm in Graph
7. Dijkstra's Algorithm in Graph
8. Kruskal's Algorithm in Graph
Congratulations! You've now learned the basics of Depth-First Search in graph theory. Feel free to experiment with the provided code examples and explore further applications of DFS in your projects.
Comments
Post a Comment