알고리즘 스터디 - 너비우선탐색(BFS), 깊이우선탐색(DFS)

너비우선탐색(BFS)이란?

• 너비우선탐색(BFS : Breadth-first search) 알고리즘은 그래프나 트리를 탐색하는데 자주 사용되는 알고리즘이다. Traversing은 가로지르다, 횡단하다라는 의미를 가지고 있지만 그래프의 각 노드를 방문하는 의미를 가지고 있다. 너비우선탐색은 트리 또는 그래프의 각 요소를 탐색하기 위해 재귀 알고리즘을 사용한다. 그래서 BFS 파이썬은 딕셔너리나 리스트 같은 데이터 구조를 이용하기도 한다.

BFS 알고리즘

• BFS 알고리즘을 알기전에 Rubik 큐브를 살펴보자. 루빅 큐브는 전체 색상에서 단일 색상으로 변환하는 경로를 찾는 것으로 간주된다. 따라서, 루빅 큐브를 그래프와 비교하면 큐브의 가능한 상태는 그래프의 노드에 해당하고 큐브의 가능한 동작은 그래프의 가장자리에 해당한다고 말할 수 있다.

• 너비 우선 탐색이 그래프의 각 노드를 탐색하는 과정이니 표준 BFS 알고리즘은 2개의 파트로 나누어 그래프의 각 노드 및 정점을 탐색하게 된다. 1) Visited 2) Not Visited 그래서 BFS 알고리즘의 목표는 사이클을 형성하지 않고 모든 정점을 방문하는 것이다.

• BFS는 한 노드에서 출발하여 모든 노드를 체크하게 되는데 방문한 노드를 담기 위해서 BFS는 큐 방식을 사용하게 된다.

BFS 알고리즘 과정

1. 처음에 그래프의 정점 중 하나를 큐 뒤쪽에 넣으면서 시작
2. 큐의 첫 아이템을 가지고 방문한 리스트로 추가함
3. 정점의 인접한 노드 리스트를 생성하고 방문되지 않은 정점을 큐의 뒤쪽에 추가함
4. 큐가 비어질 때까지 2번과 3번 과정을 반복함

큐를 생성
방문한 곳을 v로 체크하고 v를 Q로 넣음
whild Q가 비어질때까지
	Q의 u head를 제거
    방문하지 않은 u의 이웃들을 꺼내 마크를 함

BFS 알고리즘 feat. Python

graph = {
	'5' : ['3','7'],
	'3' : ['2', '4'],
	'7' : ['8'],
	'2' : [],
	'4' : ['8'],
	'8' : []
}

# 방문한 노드를 집어넣는 리스트
visited = []

# 큐를 생성
queue = []

# BFS 함수 생성
def bfs(visited, graph, node):
	visited.append(node)
    queue.append(node)
    
    # 각 노드를 방문하기 위한 루프를 생성
    while queue:
    	m = queue.pop(0)
        print(m, end=" ")
        
        for neighbour in graph[m]:
        	if neighbour not in visited:
            	visited.append(neighbour)
                queue.append(neighbour)

# Driver Code
print("Following is the Breadth-First Search")
bfs(visited, graph, '5')

깊이우선탐색(DFS)이란?

• 깊이우선탐색(DFS : Depth First Search) 은 너비 우선 탐색 처럼 그래프나 트리의 모든 정점을 살펴보는 방식이다. 우리가 DFS에 대해서 알기전에 우리가 미로를 푼다고 생각을 해보자. 우리는 끝이 발견될때까지 길을 계속 가는 경향이 있다. 끝에 다다르면 우리는 이전에 시도하지 못했던 길을 볼때까지 돌아오게 된다. 그리고 나서 새로운 길을 찾게 되고 이러한 것을 반복하는 것을 깊이우선탐색이라고 할 수 있다.

• 깊이 우선 탐색은 백트래킹 컨셉을 사용하는 재귀함수이다. 모든 노드들을 탐색하며 포함하고 잠재한 곳이 있다면 앞으로 가고 막혔다면 백트래킹한다. 여기에서 백트래킹은 일단 우리가 앞으로 움직이고 이전 길을 따라 더이상 길이 없을 때, 우리는 동일한 길을 되돌아와 다른 노드로 횡단하는 것을 말한다. 모든 방문되지 않은 노드가 방문될 때까지 현재 길에서 방문하게 되고 모든 노드는 진행하게 된다.

• 깊이우선탐색의 재귀 방법 핵심은 스택을 사용하는 것이다. 표준 깊이우선탐색은 그래프의 모든 정점을 1) Visited 2) Not Visited로 구분하며 정리하게 된다. 이 알고리즘의 목적은 모든 정점을 방문하고 사이클을 형성하지 않는 것이다.

DFS 알고리즘 과정

1. 우리는 그래프의 정점 중 하나를 스택의 위로 집어넣게 됨
2. 스택의 최고 높이 아이템에다가 방문한 정점을 집어넣음
3. 그 다음 정점의 인접한 노드의 리스트를 생성하고 이 방문한 리스트에 없는 노드 정점은 스택의 top에 더해짐
4. 마지막으로 스택이 빌 때까지 2번, 3번 과정을 반복함

DFS(G, u)
	u.visited = true
    for each v in G.adj[u]
    	if v.visited == false
        	DFS(G, v)

init() {
	For each u in G:
    	u.visited = false
    For each u in G
    	DFS(G, u)
}

DFS 알고리즘 feat. Python

# 인접한 노드를 포함하는 딕셔너리를 시용
graph = {
  '5' : ['3','7'],
  '3' : ['2', '4'],
  '7' : ['8'],
  '2' : [],
  '4' : ['8'],
  '8' : []
}

# 그래프의 방문된 노드를 추적하는 세트
visited = set()

# DFS 함수
def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '5')