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

: 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 : 특정한 경로로 탐색하다 특정 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘 : 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작 : 가장 깊숙히 위치하는 노드에 닿을때까지 탐색(확인)하는 것

• 사용 자료구조 : 스택 → 실제구현은 스택을 사용하지 않아도 재귀로 가능

• 동작과정

  1. 탐색 시작 노드를 스택에 삽입후 방문처리
  2. 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
  3. 2번의 과정을 더이사 수행할수 없을때까지 반복

• 탐색을 수행할때 데이터 개수 N →O(N)

• 소스코드

  #DFS 메서드 정의
  def DFS(graph, v, visited):
  	#현재노드를 방문 처리
  	visited[v]=True
  	#현재 노드와 연결되 다른 노드를 재귀적으로방문
  	for i in graph[v]:
  		if not visited[i]:
  			DFS(graph,i,visited)
  

BFS(Breadth-First Search) : 너비 우선 탐색

: 그래프에서 가까운 노드부터 탐색하는 알고리즘

• 사용자료구조 : 큐

• 동작과정

  1. 탐색 시작 노드를 큐에 삽입하고 방문처리
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드중 방문하지 않은 노드를 모두 큐에 삽입후 방문 처리
  3. 2번의 과정을 더이상 수행할수 없을때까지 반복

• 탐색을 수행할때 데이터 개수 N →O(N) : 그러나 일반적인 경우 실제 수행시간은 DFS 보다 좋은 편

• 소스코드

  from collections import deque
  
  #BFS 메서드 정의
  def BFS(graph, start, visited):
  	#큐(Queue) 구현을 위해 deque 라이브러리 사용
  	queue=deque([start])
  	#현재노드 방문처리
  	visited[start]=True
  	#큐가 빌때까지 반복
  	while queue:
  		#큐에서 하나의 원소를 뽑음
  		v= queue.popleft()
  		#해당 원소와 연결된, 아직 방문하지 않은 원소들 큐에 삽입
  		for i in graph[v]:
  			if not visited[i]:
  				queue.append(i)
  				visited[i]=True