1. Introduction
Recently, many companies have been conducting coding tests using algorithms. In these coding tests,
graph traversal algorithms like DFS (Depth-First Search) and BFS (Breadth-First Search) are frequently featured.
This article will summarize the basic concepts of DFS and BFS, and based on this, present an algorithm problem
and explain the problem-solving process in detail.
2. Overview of DFS and BFS
2.1 DFS (Depth-First Search)
DFS is a method that starts from a vertex of the graph and explores as far as possible along each branch
before backtracking to the last visited vertex to continue the exploration. It can be implemented using
a stack data structure or a recursive function. The process of DFS is as follows:
- Add the starting vertex to the stack and mark it as visited.
- Pop a vertex from the top of the stack and add an unvisited adjacent vertex to the stack.
- Repeat the above steps until all vertices have been explored.
2.2 BFS (Breadth-First Search)
BFS is a method that starts from a vertex of the graph and explores all its adjacent vertices first,
and then explores the adjacent vertices of those adjacent vertices. It is implemented using a queue data structure.
The process of BFS is as follows:
- Add the starting vertex to the queue and mark it as visited.
- Dequeue a vertex and add unvisited adjacent vertices of that vertex to the queue.
- Repeat the above steps until all vertices have been explored.
3. Introduction to Algorithm Problem
Problem: Path Finding
Here is a problem of finding a path using DFS and BFS.
Problem Statement: Given a graph and two vertices A and B,
check if there exists a path from A to B.
The graph is provided in the form of an adjacency list.
input:
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D', 'E'],
'D': ['F'],
'E': [],
'F': []
}
start = 'A'
end = 'F'
output: True (There exists a path from A to F)
4. Problem-Solving Process
4.1 Finding Path using DFS
The method to find a path using DFS is as follows.
It can be implemented using a recursive function and a set data structure can be used to keep track of visited vertices.
def dfs(graph, start, end, visited):
if start == end:
return True
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
if dfs(graph, neighbor, end, visited):
return True
return False
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D', 'E'],
'D': ['F'],
'E': [],
'F': []
}
start = 'A'
end = 'F'
visited = set()
result = dfs(graph, start, end, visited)
The above code allows for path finding using DFS.
Initially, when the starting vertex A is given, it checks the visit status of that vertex and then explores the adjacent vertices
using recursive calls. If it reaches vertex F and returns True, it signifies that a path exists.
4.2 Finding Path using BFS
The method to find a path using BFS involves maintaining a record of visited vertices using a queue.
from collections import deque
def bfs(graph, start, end):
queue = deque([start])
visited = set([start])
while queue:
vertex = queue.popleft()
if vertex == end:
return True
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return False
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D', 'E'],
'D': ['F'],
'E': [],
'F': []
}
start = 'A'
end = 'F'
result = bfs(graph, start, end)
Using the above code implemented for BFS, we can explore each adjacent vertex one by one
through the queue to check if there is a path from A to F.
The queue is used during the exploration process, and it also keeps track of visited vertices.
5. Conclusion
DFS and BFS are distinct search methods, each suitable for various problems depending on their characteristics.
If one wants to explore the depth of the structure first, DFS is advantageous, while BFS is preferable for finding the shortest path.
This article demonstrated the implementation and differences between the two algorithms through a simple path-finding problem.
Based on this foundation, one can attempt to tackle more complex algorithm problems.
6. References
- Data Structures and Algorithms in Python by Michael T. Goodrich
- Introduction to Algorithms by Thomas H. Cormen
- Python Documentation: https://docs.python.org/3/