DFS 깊이우선탐색, BFS 넓이우선탐색

 

DFS (Depth-First Search)

---

DFS는 Depth-First Search의 약자로, 깊이 우선 탐색이다. 
시작점에서 주변 노드를 찾은 후 (이 때 탐색하는 노드는 문제 조건마다 다르지만 대부분 오름차순으로 진행) 가장 깊은 노드까지 탐색하는 방법이다. 

구현방법: 

재귀함수를 사용하는데, 그래프가 주어지면 첫 방문 노드의 visited 인덱스 값을 True로 바꿔준다. 
이후 노드 방문을 출력해주고, 그 노드의 인접 노드 값들을 for문을 돌려서 인접 노드들 중 방문하지 않은 노드들만 다시 DFS 함수를 실행한다.

 

코드구현:

 

def dfs(graph, v, visited):
	visited[v] = True
    print(v, end = ' ')
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

graph = [
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7,],
  [2,6,8],
  [1,7],
]

visited = [False] * 9

dfs(graph, 1, visited)

 

출력:

1 2 7 6 8 3 4 5

 

 

 

BFS (Breadth-First Search)

---

 

BFS는 Breadth-First Search로 넓이 우선 탐색이다. 탐색을 할 때 깊은곳까지 들어가기보다는 얕은 곳부터 순서대로 훑으면서 들어가는 느낌이다. 예를들어 위 사진의 경우 1번노드를 시작점으로 할 때, 2번을 탐색하고 그 다음 3번을 탐색한다. DFS에서는 2번 후 7번을 탐색한 것과 다른 내용이다. 

구현 방법:

BFS에서는 Queue, 큐를 사용한다. 탐색을 진행하면서 새로운 노드를 발견하면, 큐에 추가하고 그 노드에서의 탐색을 완료하면 큐에서 그 노드를 제거해준다. 결과적으로 큐가 전부 비게되면 탐색을 모두 끝마친 것이라 할 수 있다.

코드 구현:

 

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
  
graph = [
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7,],
  [2,6,8],
  [1,7],
]

visited = [False] * 9

bfs(graph, 1, visited)

 

출력:

 

1 2 3 8 7 4 5 6