5-2. 탐색 알고리즘 DFS/BFS

DFS (Depth-First Search)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

스택 자료구조 혹은 재귀 함수를 이용함

 

동작과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리 함

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리
    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄

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

 

def dfs(graph, v, visited):
	# 현재 노드 방문 처리
	visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i ,visited)
            
graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]]
# 각각 1번노드와 연결, 2번노드와 연결, 3번 노드와 연결 ...

visited = [False] * 9

dfs(graph, 1, visited)

 

BFS (Breadth-First Search) - 최단거리 등

그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

큐 자료구조를 이용함

 

동작과정

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

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

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

from collections import deque

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
            
graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]]
# 각각 0번 노드부터 1번노드와 연결, 2번노드와 연결, 3번 노드와 연결 ...

visited = [False] * 9

bfs(graph, 1, visited)