DFS, BFS의 개념

DFS, BFS의 개념

노드1을 시작노드로 하는 그래프

DFS

DFS는 스택을 이용하는 알고리즘이다.

노드의 탐색 순서(=스택에 들어간 순서)는 다음과 같다. (작은 노드 먼저 방문처리)

1 → 2 → 7 → 6 → 8 → 3 → 4 → 5

DFS 예제 (재귀 함수 이용)

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] ] visited = [False] * 9 dfs(graph, 1, visited)

출력 결과

1 2 7 6 8 3 4 5

BFS

BFS는 큐를 이용하는 알고리즘이다.

노드의 탐색 순서(=큐에 들어간 순서)는 다음과 같다. (작은 노드 먼저 방문처리)

1 → 2 → 3 → 8 → 7 → 4 → 5 → 6

BFS 예제 (큐 자료구조 이용)

from collections import deque def bfs(graph, start, visited): # 큐 구현을 위해 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 # 각 노드가 연결된 정보 graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] visited = [False] * 9 bfs(graph, 1, visited)

출력 결과

1 2 3 8 7 4 5 6

from http://ympark4.tistory.com/18 by ccl(A) rewrite - 2021-09-22 16:00:19