[알고리즘] BFS, DFS 파이썬 구현

1. BFS: Breadth-First Search 너비 우선 탐색

BFS에서는 큐를 활용한다. 너비 우선 탐색이라는 개념과 FIFO의 특징을 생각해 보면 쉽게 이해할 수 있다. 큐를 사용하여 큐에 먼저 들어간 노드들을 먼저 팝해주는 것.

from collections import deque

def bfs(graph, node, visited):
    queue = deque([node]) # 첫 번째 노드로 큐를 만들어줌
    visited[node] = True # 해당 노드 방문 기록
    
    while queue: # 큐에 요소가 남아있는 동안
        n = queue.popleft() # 큐의 앞에서 요소 빼줌
        print(n, end = " ") # 해당 요소 출력
        for i in graph[n]: # 해당 요소의 자식 노드들에 대하여
            if not visited[i]: # 큐 안에 없으면(=아직 방문한 적 없는 노드라면)
                queue.append(i) # 큐에 삽입한 후
                visited[i] = True # 방문했음을 기록
            
graph = [
    [], # 노드 넘버와 인덱스를 맞춰주기 위해 빈 리스트 삽입(편의를 위한 것임)
    [2, 3],
    [1, 8],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7, 8],
    [6, 8],
    [2, 6, 7]
    ]

visited = [False] * len(graph)

bfs(graph, 1, visited)

참고 코드: https://heytech.tistory.com/56

[Python] BFS 알고리즘 개념 및 실습

2. DFS: Depth-First Search 깊이 우선 탐색

dfs에서는 스택을 사용한다. 재귀호출을 사용하면 쉽게 구현이 가능한데, 재귀호출로써 나중에 들어간 노드들을 먼저 팝해주는 식(LIFO)이다.

def dfs(graph, node, visited):
    visited[node] = True
    print(node, end = " ")
    for i in graph[node]: # 선택된 노드의 모든 자식 노드에 대해
        if not visited[i]: # 해당 자식노드를 방문한 적이 없다면
            dfs(graph, i, visited) # 재귀적으로 해당 자식노드를 탐색하라

# 자식노드의 자식노드들 먼저 탐색해준 후 다른 자식노드로 넘어가기 때문에 깊이 우선 탐색

graph = [
    [], # 노드 넘버와 인덱스를 맞춰주기 위해 빈 리스트 삽입(편의를 위한 것임)
    [2, 3],
    [1, 8],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7, 8],
    [6, 8],
    [2, 6, 7]
    ]

visited = [False] * len(graph)
dfs(graph, 1, visited)

참고 코드: https://heytech.tistory.com/55?category=464168 

[알고리즘] 깊이 우선 탐색(DFS) 알고리즘에 대해 알아보자!(+Python 구현)