[알고리즘] DFS vs. BFS

 

 

>> 공통점 : visited check 

 

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backing up. It typically uses a stack data structure (either explicitly or via recursion) to keep track of the nodes to be visited. Here’s how it works:

1. Start at the selected node (typically the root in a tree).
2. Mark the node as visited and push it onto the stack.
3. Go to an adjacent unvisited node, mark it as visited, and push it onto the stack.
4. Repeat until you reach a node with no unvisited adjacent nodes, then you pop it from the stack.
5. Continue the process until the stack is empty.

This method tends to go deep into the graph quickly and is particularly useful for tasks like checking if a path exists between two nodes or finding strongly connected components.

>> recursion, stack(iter)

>> Back-Tracking (탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다, 가능성이 없는 경우에는 즉시 후보를 포기)

>> DFS는 왔던 길을 다시 가지 않음

>> 트리의 가지치기 (Prunning)에도 사용이 되며, 이는 트리의 탐색  최적화 문제와도 연관이 있음

 

Code templelate

1. DFS recursive

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()  # Initialize the visited set if it's the first call

    visited.add(start)
    print(start)  # Process the node (e.g., print or collect it)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Example Graph
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['G'],
    'F': [],
    'G': []
}

# Using the DFS function
visited = set()
dfs(graph, 'A', visited)

 

> defaultdict or list 로 그래프 생성

 

 

2. DFS iter(stack)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            print(vertex)  # Process the node
            visited.add(vertex)
            # Add all unvisited neighbors to the stack
            # Reverse to maintain similar order as recursive
            stack.extend(reversed([n for n in graph[vertex] if n not in visited]))
            # Or push > stack.push() all neighbors

# Using the DFS function
dfs_iterative(graph, 'A')

 

 

Breadth-First Search (BFS)

BFS explores all the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. It typically uses a queue to keep track of the nodes to be explored. Here’s the process:

1. Start at the selected node and mark it as visited.
2. Place it in a queue.
3. While the queue is not empty, do the following:
   • Remove the front of the queue and call it the current node.
   • For each adjacent node:
     • If it has not been visited, mark it as visited and enqueue it.

BFS is used for finding the shortest path from the starting node to other nodes in an unweighted graph because it explores all neighbors at the current depth, before moving on to nodes at the next depth level.

Both algorithms are essential in many computer science problems and have their unique use cases depending on the problem requirements.

>> queue(iter) / recursion 불가능

>> Dijkstra(Greedy), Shortest-path

 

Code Template

Only iter(queue)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])  # Use deque for efficient FIFO queue operation

    while queue:
        vertex = queue.popleft()  # Remove from front of the queue
        if vertex not in visited:
            print(vertex)  # Process the node
            visited.add(vertex)
            # Add all unvisited neighbors to the queue
            queue.extend([n for n in graph[vertex] if n not in visited])

# Using the BFS function
bfs(graph, 'A')

 

> deque 사용 (default dict보다 유용)

 

 

Use Case

• 일반적으로 DFS가 더 많이 사용됨
• BFS는 쓰임새가 더 적으며, 최단 거리(경로)를 찾는 다익스트라에 주로 사용