[Algorithm] BFS, DFS

그래프 탐색 알고리즘의 두가지 BFS, DFS이다. 

 

그래프 : 정점(node)과 정점들을 이어주는 간선(edge)으로 이루어진 자료구조

 

 

 

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

 

그래프에서 인접한 노드부터 우선적으로 탐색하는 알고리즘

시작 정점으로부터 인접한 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하는 방법

- 주로 Queue를 이용하여 구현

 

BFS 탐색 순서

 

 

from collections import deque
check = [False]*(v+1)	# 각 노드 방문 정보 리스트


def bfs(x, check): # x: 현재 노드
    queue = deque([x])
    check[x] = True	# x 노드 방문 표시
    while queue:	# queue가 빌 때까지
        k = queue.popleft()
        print(k, end=' ')
        for y in graph[k]:	# 이 코드에서는 graph는 주어지지 않았지만 인접 리스트가 주어져야 함
            if not check[y]:	# x 노드와 연결된 방문하지 않은 원소들을 queue에 삽입
                queue.append(y)
                check[y] = True
                
bfs(1, check)

 

 

 

 

 

 

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

 

그래프에서 깊게 내려간 다음, 더 이상 깊게 갈 곳에 없을 때 옆으로 이동

임의의 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

- 주로 STACK or 재귀 함수를 이용하여 구현

 

DFS 탐색 순서

 

 

check = [False]*(v+1)	# 각 노드 방문 정보 리스트

def dfs(x, check):	
    check[x] = True	# x 노드 방문 표시
    print(x, end=' ')
    for k in graph[x]:	# x 노드와 연결된 아직 방문하지 않은 노드를 재귀호출
        if not check[k]:
            dfs(k, check)
            
dfs(1, check)

 

---

 

• 문제 유형별 유리한 탐색 방법 

모든 정점을 방문	DFS, BFS
최단 거리	BFS
경로의 특징	DFS

 

 

• BFS, DFS 문제 유형 리스트

'[Python] Baekjoon/Graph(그래프)' 카테고리의 글 목록