깊이 우선 탐색_DFS, 넓이 우선 탐색_BFS

DFS(Depth-First Search)

• 깊이 우선 탐색 알고리즘
• 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문 한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘
• DFS는 스택 자료구조를 이용한다(보통 재귀함수를 이용해 DFS를 구현한다.)
• 동작과정
  1. 탐색 시작노드를 스택에 삽입 후 방문 처리를 한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접노드가 없으면 최상단 노드를 꺼낸다.
  3. 2를 수행할 수 없을때까지 반복한다.

def DFS(graph,v,visit):
	visited[v] = True
	print(v)
	for i in graph[v]:
		if not visited[i]:
			DFS(graph,i,visited)

BFS(Breadth-First Search)

• 너비 우선 탐색 알고리즘
• 가까운 노드부터 탐색하는 알고리즘
• 큐를 이용해서 구현하는 것이 정석이다.
• 동작과정
  1. 탐색 시작노드를 큐에 삽입 후 방문처리를 한다.
  2. 큐에서 노드를 꺼내 해당 노드의 인접노드중 방문하지않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
  3. 2의 과정을 수행할 수 없을때까지 반복한다.

from collections import deque

def BFS(graph,start,visited):
	queue = deque([start])
	visited[start] = True
	while queue:
		v = queue.popleft()
		print(v)
		for i in graph[v]
			if not visited[i]:
				queue.append(i)
				visited[i] = True