[Algorithm] 너비 우선 탐색 BFS / 깊이 우선 탐색 DFS

 

 

개인적으로 어려워 하는 알고리즘,,

 

알고리즘

BFS는 FIFO를 원칙으로 하는 Queue로 구현한다.

탐색을 시작하는 첫 노드(root)를 queue에 넣고 탐색을 시작한다.

A. queue에서 노드를 꺼낸다.

B. 꺼낸 노드와 연결된 노드 중 방문하지 않은 노드를 방문하고 queue에 넣는다.

queue에 노드가 없어질 때 까지 AB반복

 

구현

 

 

def bfs(graph, root):
	visit = list()
	queue = [root]

    #AB반복
	while queue:
		temp = queue.pop(0)
		if temp not in visit:
			print(temp)
			visit.append(temp)
			queue.extend(graph[temp])

 

 

알고리즘

DFS는 LIFO를 원칙으로 하는 Stack으로 구현한다.

탐색을 시작하는 첫 노드(root)를 stack에 넣고 탐색을 시작한다.

A. stack의 최근 노드를 확인한다.

B. 확인한 노드와 연결된 노드 중 인접한 노드를 방문하고 stack에 넣는다.

C. 인접한 노드 중 방문하지 않은 노드가 없다면 stack에서 노드를 하나 꺼낸다.

stack이 노드가 없어질 때 까지 ABC 반복

 

구현

 

 

def dfs(graph, root):
	visit = list()
	stack = [root]
 
	#ABC반복
	while stack :
		temp = stack.pop()
		if temp not in visit :
			print(temp)
			visit.append(temp)
			stack.extend(graph[temp])

 

graph info

 

code

graph = {'A': set(['B', 'C', 'E']),
         'B': set(['A', 'D', 'F']),
         'C': set(['A', 'G']),
         'D': set(['B']),
         'E': set(['A', 'F']),
         'F': set(['B', 'E']),
         'G': set(['C'])}