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

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

• 스택 or 재귀함수 이용 깊은 노드 우선 탐색
• 동작과정
  ① 탐색 시작 node - 스택에 삽입, 방문 처리
  ② 스택 최상단 node - 미방문 인접 node O, 스택에 넣고 방문 처리.
                                미방문 인접 node X, 스택에서 최상단 node pop
  ③ 위 과정 반복

def dfs(graph, v, visited):
    # 현재 노드 방문처리
    visited[v] = True
    print(v, end=' ')
    
    # 인접 노드 재귀적 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
 
# 각 노드 연결된 정보 (2차원 리스트)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보 (1차원 리스트)
visited = [False]*9

# 정의된 DFS 함수 호출
dfs (graph, 1, visited)

 

 

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

• 큐 이용 가까운 노드 우선 탐색
• 동작과정
  ① 탐색 시작 node - 큐에 삽입, 방문 처리
  ② 큐 최하단 node - 미방문 인접 node O, 모두 큐에 삽입 방문 처리.
                             미방문 인접 node X, 다음 node로
  ③ 위 과정 반복

from collections import deque

def bfs(graph, start, visited):
    # 큐 구현
    queue = deque([start])
    
    # 현재 node 방문 처리
    visited[start] = True
    
    # 큐 empty 될 때까지 반복
    while queue:
    	# 최하단 node pop
        v = queue.popleft()
        print(v, end=' ')
        
        # 인접 node 큐에 삽입
        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)