파이썬, DFS, BFS 코드와 동영상

 

파이썬, DFS, BFS 코드와 동영상

글. 오상문 sualchi@daum.et 

 

그래프 경로를 탐색하는 알고리즘으로 대표적인 게 DFS와 BFS가 있습니다.

 

  DFS(깊이 우선 탐색; Depth-First Search)

  BFS(너비 우선 탐색; Breadth-First Search)

 

DFS는 시작 노드에서 한쪽 방향으로 가장 깊은 곳까지 탐색하고, 돌아오면서 다른 곳을 탐색하는 방식입니다.

BFS는 시작 노드와 가장 가까운 노드를 먼저 방문하고, 방문 노드들과 가까운 노드를 탐색하는 방식입니다.

 

다음은 DFS, BFS와 관련된 동영상 링크는 아래쪽에 있으니 참고하세요. 

 

다음 그래프 구조는 동영상에 나온 예제 그림입니다.

 

 

둥근 지점을 노드(정점)이라고 부릅니다. 

노드를 연결하는 선은 엣지(간선)이라고 부릅니다.

 

1번을 시작 노드로 할 때 방문 순서는 다음과 같습니다.

두 방식에서 탐색하는 순서가 다른 것을 알 수 있습니다.

 

DFS : 1 2 7 6 8 3 4 5

BFS : 1 2 3 8 7 4 5 6

 

DFS 파이썬 예제 코드는 다음과 같습니다. 

# DFS: Depth-First Search
graph = [[],        # 0번은 사용 안함
        [2, 3, 8],
        [1, 7],
        [1, 4, 5],
        [3, 5],
        [3, 4],
        [7],
        [2, 6, 8],
        [1, 7]]
visited = [False]*9    # 8개 노드의 방문 정보 (0번은 사용 안함)
def dfs(graph, v, visited):
    visited[v] = True
    print(v, end = ' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
dfs(graph, 1, visited)
# 1 2 7 6 8 3 4 5

 

BFS 파이썬 예제 코드는 다음과 같습니다.

# BFS: Breadth First Search
from collections import deque
graph = [[],         # 0번은 사용 안함
        [2, 3, 8],
        [1, 7],
        [1, 4, 5],
        [3, 5],
        [3, 4],
        [7],
        [2, 6, 8],
        [1, 7]]
visited = [False]*9  # 8개 노드의 방문 정보 (0번은 사용 안함)
def bfs(graph, start, visited):
    queue = deque([start]) 
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end = ' ')        
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
bfs(graph, 1, visited)
# 1 2 3 8 7 4 5 6 

 

 

youtu.be/PqzyFDUnbrY