BFS(Breadth First Search) & DFS(Depth First Search)
(참고 자료 : 패스트캠퍼스 이준희님의 알고리즘 강의)
1. BFS vs DFS
너비 우선 탐색 : BFS(Breadth First Search)
정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식
깊이 우선 탐색 : DFS(Depth First Search)
BFS 방식: A - B - C - D - G - H - I - E - F - J 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함
DFS 방식: A - B - D - E - F - C - G - H - I - J 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순화함
2. 파이썬으로 BFS, DFS 그래프 표현
파이썬 딕셔너리와 리스트로 그래프 표현 가능
bfs 그래프
dfs 그래프
한 노드에 연관되어 있는 노드들을 모두 적는다.
graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']
print(graph)
아래는 결과값이다.
{'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'G', 'H', 'I'],
'D': ['B', 'E', 'F'],
'E': ['D'],
'F': ['D'],
'G': ['C'],
'H': ['C'],
'I': ['C', 'J'],
'J': ['I']}
bfs, dfs모두 그래프 표현은 같다.
하지만 알고리즘 구현에서 bfs는 need_visit queue를 사용하는 반면,
dfs는 need_visit stack을 사용하는 것이 특징이다.
3. BFS 탐색 순서 알고리즘 구현
bfs 알고리즘에서의 visited큐, need_visit큐 사용 예시
visited queue와 need_visit queue(두 개의 큐)와
need_visit.pop(0)으로 뽑은 node(한개의 temp)를 사용해서 bfs 탐색 순서 알고리즘을 구현할 수 있다.
def bfs(graph, start_node):
visited = list()
need_visit = list()
need_visit.append(start_node)
while need_visit:
node = need_visit.pop(0)
if node not in visited:
visited.append(node)
need_visit.extend(graph[node])
return visited
print(bfs(graph, 'A'))
결과값
['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']
4. DFS 탐색 순서 알고리즘 구현
visited queue(큐), need_visit stack(스택)과 need_visit.pop()으로 뽑은 node(한개의 temp)를 사용해서 dfs 탐색 순서 알고리즘을 구현할 수 있다.
def dfs(graph, start_node):
visited, need_visit = list(), list()
need_visit.append(start_node)
while need_visit:
node = need_visit.pop()
if node not in visited:
visited.append(node)
need_visit.extend(graph[node])
return visited
print(dfs(graph, 'A'))
결과값
['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']
5. 시간 복잡도
일반적인 BFS, DFS 시간 복잡도
간선 수: E 위 코드에서 while need_visit 은 V + E 번 만큼 수행함
