[Algorithm/Python] DFS(Depth First Search) / BFS(Breadth First Search) 구현 정리(2)

BFS(Breadth First Search)

BFS는 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 탐색하는 알고리즘이다.

 

BFS를 구현할 때는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다.

 

# 동작 방식

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

deque 라이브러리 사용 => 시간 복잡도 O(N)

일반적으로 bfs가 더 빠르다.

 

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐(Queue) 구현을 위해 deque 라이브러리 사용
	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
               	
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
	[],
    [2, 3, 8],
    [1, 7],
	[1, 4, 5],
    [3, 5],
	[3, 4],
    [7],
	[2, 6, 8],
    [1, 7]
]

# 각 노드가 방문한 정보를 리스트 자료형으로 표현(1차원 리스트)
 visited = [False] * 9
 
 # 정의된 BFS 함수 호출
 bfs(graph, 1, visited)
 
 # 1 2 3 8 7 4 5 6

 

DFS - 스택으로 동작, 재귀 함수 이용

BFS - 큐로 동작, 큐 자료구조 이용