# 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);
}
}

## Time and Space Complexity

Time Complexity:

- In the worst-case scenario, where all nodes and edges are traversed, the time complexity of DFS is O(|V| + |E|), where |V| represents the number of nodes (vertices) in the graph and |E| represents the number of edges. This is because DFS visits each node and each edge once.

- The time complexity may vary based on the specific implementation and the data structure used to represent the graph. If an adjacency list is used, the time complexity for accessing neighbors of a node is O(1) on average, resulting in an efficient overall time complexity.

Space Complexity:

- The space complexity of DFS is determined by the auxiliary data structures used during the traversal.

- In the case of using an adjacency list to represent the graph, the space complexity is O(|V| + |E|), as the adjacency list requires space for each node and its associated edges.

- Additionally, the space complexity of the stack used to keep track of visited nodes in the iterative implementation is O(|V|) in the worst case, where all nodes are pushed onto the stack.

- Therefore, the overall space complexity of DFS is O(|V| + |E|) in most cases.

It's worth noting that if the graph is represented by an adjacency matrix instead of an adjacency list, the space complexity of the algorithm would be O(|V|^2) since an adjacency matrix requires space for each pair of nodes, even if there is no direct edge between them.

## Advantages

1. Simplicity: DFS is relatively easy to understand and implement. It follows a simple recursive or iterative approach, making it accessible to beginners.

2. Memory Efficiency: DFS typically uses less memory compared to breadth-first search (BFS) since it only needs to store information about the current path and backtrack when necessary. It uses a stack (or recursion stack) to keep track of nodes, which requires less memory than the queue used in BFS.

3. Early Solution Detection: DFS can often find a solution faster than BFS in certain scenarios. Since DFS explores paths deeply before backtracking, it may reach a solution closer to the starting point earlier than BFS, which explores all neighbors at the current level before moving to the next level.

4. Topological Sorting: DFS can be used to perform a topological sort on a directed acyclic graph (DAG). This sorting order is useful in various applications, such as determining dependencies, scheduling tasks, or building efficient algorithms for processing graphs.

## Disadvantages

1. Completeness in Infinite Graphs: DFS is not complete in infinite graphs or graphs with infinite branches. If there is an infinite branch in the graph, DFS may get trapped in an infinite loop and fail to terminate.

2. Suboptimal Solution: DFS may find a suboptimal solution if the problem involves finding the shortest path or the optimal solution. This is because DFS does not consider the length or weight of edges and simply explores paths until it reaches the goal, which might not be the shortest or most optimal path.

3. May Get Stuck in Deep Paths: DFS tends to go deeply into paths before exploring other alternatives. In graphs with deep branches or paths, DFS may explore a large portion of the graph before backtracking, potentially leading to inefficient search and slower performance.

4. Lack of Breadth-First Exploration: DFS does not systematically explore the graph in a breadth-first manner. This means that DFS may not be suitable for certain problems that require a breadth-first search approach, such as finding the shortest path between two nodes.

It's important to consider these advantages and disadvantages of DFS when deciding whether to use it for a specific problem or when choosing between DFS and other graph traversal algorithms.