What is DFS Search
Depth-First Search is a graph traversal algorithm used to explore or traverse all the vertices of a graph in a depth ward motion. It starts at a selected node (often called the "source" or "root" node) and explores as far as possible along each branch before backtracking.
Here's how the DFS algorithm typically works:
1. Start by selecting a source node to begin the traversal.
2. Mark the source node as visited or "explored" to keep track of the nodes that have been visited.
3. Explore the adjacent unvisited nodes of the current node. Pick one of the unvisited neighbours, and recursively apply the DFS algorithm to that neighbour.
4. Repeat step 3 for each unvisited neighbour of the current node until there are no more unvisited neighbours.
5. If there are no more unvisited neighbours, backtrack to the previous node (the node from which the current node was explored) and continue the process from there.
6. Continue steps 3-5 until all nodes in the graph have been visited.
DFS can be implemented using either a recursive approach or an iterative approach (using a stack data structure to keep track of the nodes).
DFS is often used to solve various graph-related problems, such as finding connected components, detecting cycles, determining reachability, and exploring paths or routes within a graph.
It's worth noting that DFS does not necessarily visit nodes in a specific order unless explicitly defined. The order of visited nodes can vary depending on the graph's structure and the implementation details.
Who invented it?
The Depth-First Search (DFS) algorithm is a fundamental graph traversal technique that has been known for a long time. Its origins can be traced back to the early days of graph theory.
The concept of DFS has been described by multiple mathematicians and computer scientists throughout history. Some notable contributors to the development and popularization of DFS include:
1. Charles Pierre Trémaux (1859-1882): Trémaux, a French mathematician, is credited with the earliest known description of a depth-first search-like algorithm in 1859. His work focused on solving mazes, and he introduced the concept of marking visited paths to ensure that each path is traversed only once.
2. Édouard Lucas (1842-1891): Lucas, a French mathematician, also made significant contributions to graph theory. He explored the concept of graph traversal and introduced the idea of using depth-first search to solve puzzles and games.
3. Charles Harary (1929-2005): Harary, an American mathematician, made important contributions to graph theory and the study of algorithms. He further developed and popularized depth-first search as a fundamental graph traversal algorithm.
4. Many other mathematicians and computer scientists, including Euler, Tarjan, and Cormen, have contributed to the development and analysis of DFS and its applications in graph theory and computer science.
Pseudocode
DFS(Graph G, Node start):
// Create a stack to keep track of visited nodes
stack = new Stack()
// Mark the start node as visited and push it onto the stack
mark start as visited
stack.push(start)
// Repeat until the stack is empty
while stack is not empty:
// Pop the top node from the stack
current = stack.pop()
// Process the current node (e.g., print or perform desired operations)
process current
// Explore the unvisited neighbors of the current node
for each neighbor of current:
if neighbor is not visited:
// Mark the neighbor as visited and push it onto the stack
mark neighbor as visited
stack.push(neighbor)
// The DFS traversal is complete
In this pseudocode, G represents the input graph, and start represents the starting node for the DFS traversal. The algorithm uses a stack data structure to keep track of the nodes to be visited.
The key steps of the algorithm involve marking nodes as visited, pushing unvisited neighbors onto the stack, and popping nodes from the stack to process them. The specific processing steps for each node can be customized based on the problem or task at hand.
The key steps of the algorithm involve marking nodes as visited, pushing unvisited neighbors onto the stack, and popping nodes from the stack to process them. The specific processing steps for each node can be customized based on the problem or task at hand.
Sample Code
// C++ code snippet
// Function to perform DFS traversal
void DFS(vector>& graph, int start) {
int numNodes = graph.size();
// Create a stack to keep track of visited nodes
stack st;
vector visited(numNodes, false);
// Mark the start node as visited and push it onto the stack
visited[start] = true;
st.push(start);
while (!st.empty()) {
// Pop the top node from the stack
int current = st.top();
st.pop();
// Process the current node (e.g., print or perform desired operations)
cout << current << " ";
// Explore the unvisited neighbors of the current node
for (int neighbor : graph[current]) {
if (!visited[neighbor]) {
// Mark the neighbor as visited and push it onto the stack
visited[neighbor] = true;
st.push(neighbor);
}
}
}
}
int main() {
int numNodes, numEdges;
cout << "Enter the number of nodes in the graph: ";
cin >> numNodes;
cout << "Enter the number of edges in the graph: ";
cin >> numEdges;
vector> graph(numNodes);
cout << "Enter the edges (node u to node v):\n";
for (int i = 0; i < numEdges; i++) {
int u, v;
cin >> u >> v;
// Adding the edge to the adjacency list
graph[u].push_back(v);
// If the graph is undirected, uncomment the line below
// graph[v].push_back(u);
}
int startNode;
cout << "Enter the starting node for DFS: ";
cin >> startNode;
cout << "DFS traversal starting from node " << startNode << ": ";
DFS(graph, startNode);
return 0;
}
# Python code snippet
def DFS(graph, start):
num_nodes = len(graph)
# Create a stack to keep track of visited nodes
stack = []
visited = [False] * num_nodes
# Mark the start node as visited and push it onto the stack
visited[start] = True
stack.append(start)
while stack:
# Pop the top node from the stack
current = stack.pop()
# Process the current node (e.g., print or perform desired operations)
print(current, end=" ")
# Explore the unvisited neighbors of the current node
for neighbor in graph[current]:
if not visited[neighbor]:
# Mark the neighbor as visited and push it onto the stack
visited[neighbor] = True
stack.append(neighbor)
# Test the code
num_nodes = int(input("Enter the number of nodes in the graph: "))
num_edges = int(input("Enter the number of edges in the graph: "))
graph = [[] for _ in range(num_nodes)]
print("Enter the edges (node u to node v):")
for _ in range(num_edges):
u, v = map(int, input().split())
# Adding the edge to the adjacency list
graph[u].append(v)
# If the graph is undirected, uncomment the line below
# graph[v].append(u)
start_node = int(input("Enter the starting node for DFS: "))
print("DFS traversal starting from node", start_node, ": ", end="")
DFS(graph, start_node)
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class DFS {
public static void dfs(List> graph, int start) {
int numNodes = graph.size();
// Create a stack to keep track of visited nodes
Stack stack = new Stack<>();
boolean[] visited = new boolean[numNodes];
// Mark the start node as visited and push it onto the stack
visited[start] = true;
stack.push(start);
while (!stack.isEmpty()) {
// Pop the top node from the stack
int current = stack.pop();
// Process the current node (e.g., print or perform desired operations)
System.out.print(current + " ");
// Explore the unvisited neighbors of the current node
for (int neighbor : graph.get(current)) {
if (!visited[neighbor]) {
// Mark the neighbor as visited and push it onto the stack
visited[neighbor] = true;
stack.push(neighbor);
}
}
}
}
public static void main(String[] args) {
int numNodes = 0, numEdges = 0;
try {
System.out.print("Enter the number of nodes in the graph: ");
numNodes = Integer.parseInt(System.console().readLine());
System.out.print("Enter the number of edges in the graph: ");
numEdges = Integer.parseInt(System.console().readLine());
} catch (NumberFormatException e) {
System.out.println("Invalid input. Please enter a valid number.");
System.exit(1);
}
List> graph = new ArrayList<>();
for (int i = 0; i < numNodes; i++) {
graph.add(new ArrayList<>());
}
System.out.println("Enter the edges (node u to node v):");
for (int i = 0; i < numEdges; i++) {
try {
int u, v;
String[] edge = System.console().readLine().split(" ");
u = Integer.parseInt(edge[0]);
v = Integer.parseInt(edge[1]);
// Adding the edge to the adjacency list
graph.get(u).add(v);
// If the graph is undirected, uncomment the line below
// graph.get(v).add(u);
} catch (NumberFormatException e) {
System.out.println("Invalid input. Please enter valid node numbers.");
System.exit(1);
}
}
int startNode = 0;
try {
System.out.print("Enter the starting node for DFS: ");
startNode = Integer.parseInt(System.console().readLine());
} catch (NumberFormatException e) {
System.out.println("Invalid input. Please enter a valid node number.");
System.exit(1);
}
System.out.print("DFS traversal starting from node " + startNode + ": ");
dfs(graph, startNode);
}
}