[알고리즘/그래프] 그래프 탐색

0. 🔖 목차

---

1. 깊이 우선 탐색(DFS)
   1-1. 개념
   1-2. 그래프에서의 DFS
   1-3. 알고리즘
2. 너비 우선 탐색(BFS)
   1-1. 개념
   1-2. 알고리즘

1. 깊이 우선 탐색(DFS)

---

1-1. 개념

DFS는 가능한 한 멀리 있는 노드를 우선적으로 탐색하는 방식으로, 더 이상 진행할 수 없을 때까지 탐색을 진행한 후, 되돌아가 다른 경로를 탐색한다.

자기 반복 구조(재귀)이며 모든 노드를 방문하고자 할 때 유용하다.

혹은 깊이가 제한된, 탐색하고자 하는 요소가 단말 노드에 있을 때 사용한다.

앞서 배웠던 순열, 조합, 부분집합에서도 모든 분기(이 요소를 포함할지 안할지 등)를 고려해서 모든 경우를 찾기 위해 사용한 방법이 바로 이 DFS의 한 종류다.

아래는 DFS의 알고리즘이다.

1. 방문하지 않은 임의의 노드를 선택하여 방문
2. 현재 노드에서 방문할 수 있는 인접 노드 중 하나를 선택하여 방문
3. 더 이상 방문할 인접 노드가 없을 때까지 2를 반복
4. 더 이상 방문할 인접 노드가 없으면, 마지막으로 방문했던 노드로 돌아가서 다른 인접 노드를 찾음(Backtracking)
5. 모든 노드를 방문할 때까지 2~4를 반복합니다.

1-2. 그래프에서의 DFS

아까 순열, 조합, 부분집합에서 DFS를 사용했다고 했는데 정확히 말하면 트리 순회, 더 정확히 말하면 전위 순회를 사용했다. 쉽게 생각해서 트리 구조에서 DFS를 한 것이다.

그래프 구조에서도 DFS 알고리즘을 사용할 수 있다.

트리 자료구조에서 언급했듯 트리와 그래프의 차이점은 사이클이 있냐 없냐이다.

1-1에서 설명한 알고리즘을 보면 알겠지만 DFS는 재귀 구조를 가지고 있기 때문에 사이클이 있는 그래프에서 알고리즘을 실행하면 무한 루프에 빠질 수 있다.

따라서 1번과 2번에서 방문한 노드는 반드시 방문했다는 표시를 남겨야 하며 재귀를 할 때 방문한 노드를 재방문 하지 않는 로직을 추가해야한다.

1-3. 알고리즘

def dfs(graph, node, visited):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(graph, neighbour, visited)

# 예시 그래프
graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}
visited = set() # 방문한 노드를 추적
dfs(graph, 'A', visited)

2. 너비 우선 탐색(BFS)

---

2-1. 개념

BFS는 가까운 노드부터 우선적으로 탐색하는 방식이다.

시작 노드로부터 각 노드까지의 최단 경로나 최소 비용 문제를 해결하는 데 사용된다.

혹은 깊이가 무제한일때, 찾고자 하는 요소가 루트 근처에 있을 때 사용한다.

그래프의 모든 노드를 레벨별로 탐색하는 데 사용한다고 생각하면 쉽다.

알고리즘은 아래와 같다

1. 방문하지 않은 시작 노드를 큐에 추가하고 방문 처리
2. 큐에서 노드를 하나 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 추가하고 방문 처리
3. 큐가 빌 때까지 2를 반복
4. 모든 노드를 방문할 때까지 2~3을 반복

1-2. 알고리즘

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)
            visited.add(node)
            queue.extend(neighbour for neighbour in graph[node] if neighbour not in visited)

# 예시 그래프
graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

bfs(graph, 'A')