DFS와 BFS

깊이 우선 탐색(DFS)란?

: 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘

→ 현재 탐색 중인 노드를 기준으로 연결된 노드를 즉시 방문하는 방식

• 재귀 함수로 구현
• 스택 자료구조 이용
• 시간 복잡도 - O( V + E ) [노드 수: V, 에지 수: E]

 

 

 

깊이 우선 탐색(DFS)의 핵심 이론

1. 시작점으로부터 연결된 모든 정점을 전부 방문해야 한다.
2. 이미 방문한 정점은 다시는 방문하지 않는다.

N = 5 #노드 개수

# 인접 리스트 만들기
adj_list = [[] for _ in range(N)]
adj_list[0].append(1); adj_list[0].append(2)
adj_list[1].append(4); adj_list[1].append(3)
adj_list[2].append(3)
adj_list[3].append(0)
# [[1, 2], [4, 3], [3], [0], []]

visited = [False] * N

def dfs(node):
	global adj_list, visited

	if visited[node]:
		return
	visited[node] = True

	print(node, end=' ')

	for adj_node in adj_list[node]:
		dfs(adj_node)

dfs(0) # 시작노드를 0으로 설정
	

 

 

 

 

---

 

 

 

 

 

너비 우선 탐색(BFS)란?

: 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서

• FIFO 탐색
• Queue 자료구조 이용
• 시간 복잡도 - O( V + E ) [노드 수: V, 에지 수: E]

 

 

 

 

너비 우선 탐색(BFS)의 핵심 이론

from collections import deque

N = 5  

adj_list = [[] for _ in range(N)]
visited = [False] * N

adj_list[0].append(1)
adj_list[0].append(2)
adj_list[1].append(4)
adj_list[1].append(3)
adj_list[2].append(3)
adj_list[3].append(0)

# 시작 노드 넣기
q = deque()
q.append(0)
visited[0] = True

while q:
    node = q.popleft()
    print(node, end=' ')

    for adj_node in adj_list[node]:
        if visited[adj_node]:
            continue
        q.append(adj_node)
        visited[adj_node] = True