Depth First Search (DFS) is a type of graph traversal algorithm used to search a graph data structure. This article will cover the basics of DFS and how it works, its time and space complexities, and Python code examples of the algorithm. Additionally, this article will provide coding exercises with solutions to test the reader’s understanding of DFS.
What is Depth First Search?
Depth First Search (DFS) is a type of graph traversal algorithm used to search a graph data structure. It is a recursive algorithm that begins at the root node and explores as far as possible along each branch before backtracking. DFS is used to explore a graph data structure to find a particular node or the path between two nodes.
How Does Depth First Search Work?
Depth First Search begins by selecting a starting node, or the root node, of the graph. It then explores as far as possible along each branch before backtracking. This means that the algorithm will explore all of the nodes connected to the root node before exploring nodes connected to the nodes connected to the root node. This process is repeated until the algorithm finds the node it is searching for or all of the nodes in the graph have been explored.
To illustrate, imagine a graph that has four nodes, A, B, C, and D. A is the root node and the algorithm is searching for node D. The algorithm will begin at node A and explore all of the nodes connected to node A, which in this case is nodes B and C. It will then explore all of the nodes connected to node B and C, which in this case is node D. The algorithm will then backtrack to node C and explore all of the nodes connected to node C, which in this case is node D. Once the algorithm finds node D, it will stop and the search will be complete.
Time Complexity
Depth First Search has a time complexity of O(V + E), where V is the number of nodes in the graph and E is the number of edges in the graph. This time complexity is the same for both the best and worst case scenarios.
Space Complexity
Depth First Search has a space complexity of O(V). This means that the algorithm will take up a maximum of O(V) space in memory in the worst case scenario.
Python Code
Now that we understand the basics of DFS, we can look at some Python code that implements the algorithm. The following code is a simple implementation of the Depth First Search algorithm.
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited
# example graph
graph = {
'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])
}
dfs(graph, 'A') # {'E', 'D', 'F', 'A', 'C', 'B'}
Conclusion
In conclusion, Depth First Search (DFS) is a type of graph traversal algorithm used to search a graph data structure. It is a recursive algorithm that begins at the root node and explores as far as possible along each branch before backtracking. DFS has a time complexity of O(V + E), where V is the number of nodes in the graph and E is the number of edges in the graph. It also has a space complexity of O(V).
Exercises
Given the following graph, use Depth First Search to find the path between nodes B and F. graph = { ‘A’: set([‘B’, ‘C’]), ‘B’: set([‘A’, ‘D’, ‘E’]), ‘C’: set([‘A’, ‘F’]), ‘D’: set([‘B’]), ‘E’: set([‘B’, ‘F’]), ‘F’: set([‘C’, ‘E’]) }
Path: B -> D -> B -> E -> F
Write a function that uses Depth First Search to search a graph for a given node.
def dfs_search(graph, start, search_val):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
if vertex == search_val:
return True
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return False
Given the following graph, use Depth First Search to find all the nodes reachable from node A. graph = { ‘A’: set([‘B’, ‘C’]), ‘B’: set([‘A’, ‘D’, ‘E’]), ‘C’: set([‘A’, ‘F’]), ‘D’: set([‘B’]), ‘E’: set([‘B’, ‘F’]), ‘F’: set([‘C’, ‘E’]) }
Nodes reachable from node A: B, C, D, E, F
Write a function that uses Depth First Search to find the shortest path between two nodes in a graph.
def dfs_shortest_path(graph, start, end):
visited = set()
stack = [(start, [start])]
while stack:
(vertex, path) = stack.pop()
if vertex not in visited:
if vertex == end:
return path
visited.add(vertex)
for node in graph[vertex] - visited:
stack.append((node, path + [node]))
return None
Given the following graph, use Depth First Search to find all the nodes that are not connected to node A. graph = { ‘A’: set([‘B’, ‘C’]), ‘B’: set([‘A’, ‘D’, ‘E’]), ‘C’: set([‘A’, ‘F’]), ‘D’: set([‘B’]), ‘E’: set([‘B’, ‘F’]), ‘F’: set([‘C’, ‘E’]) }
Nodes not connected to node A: None