DFS/BFS

---

선행 학습

• 스택 (FILO)
  • python List 에서 append() 함수와 pop()함수를 이용해 쉽게 구현 가능
• 큐 (FIFO)
  • collections 의 deque 라이브러리를 사용한다

    from collections import deque

    queue= deque()

    queue.append(5)
    queue.popleft()
    queue.append(1)
    queue.append(3)
    queue.popleft()

    print(queue) # 출력
    queue.reverse()# 역순으로 바꾸기
    print(queue) # 나중에 들어온 원소부터 출력

• 재귀 함수

DFS (Depth-First Search)

- 깊이 우선 탐색이라고 부르며 깊은 부분을 우선적으로 탐색하는 알고리즘
- 주로 스택 혹은 재귀함수를 사용

    1.탐색 노드를 스택에 삽입 방문처리 함

    2. 스택 최상단 노드에 방문하지 않은 인접노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 방문하지 않은 인접노드가 없으면 최상단 노드를 꺼낸다.

    3.2번의 과정을 수행할 수 없을 때 까지 반복

예제 코드

 def dfs(graph,v,visited):
 	visited[v] = True
 	print(v,end=' ')
 	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, end = ' ')
 		for i in graph[v] : 
 			if not visited[i]:
 				queue.append(i)
 				visited[i] =True