[자료구조]BFS & DFS
카테고리: DataStructure
네트워크 문제를 풀기 위해서는 그래프로부터 정보를 추출해야한다. 특정한 방식을 따라 그래프에 있는 모든 노드(Node = Vertex)와 엣지(Edge = Link)를 확인하는 과정을 그래프 순회(Graph Traversal)이라고 한다. 그래프 순회는 모든 vertex와 edge를 한 번씩 방문한다. 일반적으로 그래프 순회는 두 가지 방법이 존재한다.
- 너비 우선 검색(Breadth-First Search, BFS)
- 깊이 우선 검색(Depth-First Search, DFS)
1. 너비 우선 검색(Breadth-First Search, BFS)
1) BFS의 개념
BFS는 그래프 내에 Layer 또는 Level로 구성된 이웃 그룹들이 있을 때 적용할 수 있는 가장 효율적인 그래프 순회 전략입니다.
- Ex)
- 링크드인 회원의 관계 네트워크는 회원을 중심으로 1단계, 2단계 커넥션과 같은 레이어로 구성됨.
BFS는 루트 노드(Root Vertex)에서 시작하여 그 인근 레이어에 있는 이웃 노드(Neighbour Vertex)들을 탐색한다. 이웃들에 대한 확인이 끝나면
다음 레이어(레벨)로 이동하여 검색 과정을 반복한다.
2) BFS 구현 with Python
초기 설정
그래프 순회는 노드들을 한 번씩만 방문해야 합니다. 따라서 방문 기록을 관리하여 앞으로 어떤 노드를 방문해야 할 지 알아야 한다.
- Visited: 방문한 노드들을 저장. Initial List는 빈 리스트
- Queue : 다음 번 검색에서 방문할 노드들을 저장한다. 리스트나 큐(queue)를 사용한다.
메인 루프
메인 루프는 큐에 있는 노드들을 하나씩 꺼내어 방문 기록을 확인한다. 방문 기록이 없다면 노드에 연결된 이웃 노드를 큐에 추가한다. 이미 방문한 적이 있다면 큐에 있는 다음 노드로 이동한다.
- How to work?
- queue에서 첫 번째 노드르르 꺼내온다.
- 해당 노드가 visited 리스트에 없다면 이를 visited에 추가한다. 그리고 이 노드의 이웃 노드 목록을 그래프에서 불러온다.
- 불러온 이웃 노드들을 queue에 추가한다.
- 메인 루프가 종료되면 그동안 방문한 모든 노드가 담긴 visited가 반환된다.
BFS는 큐(queue)를 이용한다. 큐는 선입선출(FIFO)방식으로 데이터를 관리한다.
- 그림 설명
- 레벨 1에 있는 유일한 노드인 Amin을 루트 노드로 삼아 알고리즘을 시작한다.
- 레벨 2로 이동해 Wasim, Nick, Mike를 하나씩 차례고 방문한다.
- 레벨 3의 Imran, 레벨 4의 Faras를 차례로 방문합니다.
- 순회가 종료되면 모든 노드는 visited에 저장되고 알고리즘이 종료된다.
Case 1.
[Input]
graph = {
'Amin' : {'Wasim', 'Nick', 'Mike'},
'Wasim' : {'Imran', 'Amin'},
'Imran' : {'Wasim', 'Faras'},
'Faras' : {'Imran'},
'Mike' : {'Amin'},
'Nick' : {'Amin'}}
def BFS(graph, start):
visited = []
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
neighbours = graph[node]
for neighbour in neighbours:
queue.append(neighbour)
return visited
BFS(graph, 'Amin')
[Output]
['Imran', 'Faras', 'Wasim', 'Amin', 'Mike', 'Nick']
Case 2.
[Input]
from collections import deque
graph = {
'Amin' : {'Wasim', 'Nick', 'Mike'},
'Wasim' : {'Imran', 'Amin'},
'Imran' : {'Wasim', 'Faras'},
'Faras' : {'Imran'},
'Mike' : {'Amin'},
'Nick' : {'Amin'}}
def BFS(graph, start):
visited = []
queue = deque([start])
while queue:
n = queue.popleft()
if n not in visited:
visited.append(n)
if n in graph:
temp = list(set(graph[n]) - set(visited)) ## set은 리스트 안에 리스트를 추가할때,
temp.sort() ## 괄호를 제거하고 요소만 추가하게 해주는 메서드다.
queue += temp
return " ".join(str(i) for i in visited)
BFS(graph, "Amin")
[Output]
Amin Mike Nick Wasim Imran Faras
2. 깊이 우선 검색(Depth-First Search, DFS)
1) DFS의 개념
BFS는 레이어(레벨)별로 노드를 방문한다. 이와 달리 DFS는 개별 경로를 하나씩 탐색한다. 선택한 경로의 끝에 도달하면 DFS는 그 과정에서 방문한 모든 노드들을 방문 완료 처리한다. 그리고 걸어온 길을 되돌아 나와 경로를 시작한 노드로 이동한다. 이 노드에 아직 방문하지 않은 또 다른 경로(subgraph)가 있다면 이에 대한 탐색을 시작 한다. 만약 방문할 노드가 없다면 알고리즘을 종료한다.
몇몇 그래프는 순환 경로를 가지기도 한다. Boolean flag(불 플래그)를 사용하여 노드 방문 기록을 관리하면 순환 경로에 빠지는 것을 방지할 수 있다.
2) DFS 구현 with Python
DFS는 스택(Stack)을 사용한다. 스택은 후입선출(LIFO) 방식으로 데이터를 관리한다.
- 그림설명
- 그래프의 맨 위 노드인 Amin부터 시작한다.
- 레벨 2에 있는 Wasim을 방문하고 Wasim과 연결된 레벨 3의 Imran 노드를, 그리고 레벨 4의 Imran과 연결된 노드인 Faras를 방문하고 경로의 끝에 도달한다.
- 경로를 시작했던 Amin으로 되돌아간다. 그리고 아직 방문하지 않은 레벨 2의 노드인 Nick과 Mike를 차례로 방문한다.
DFS는 Tree 자료구조에서도 이용된다.
Case 1.
[Input]
graph = {
'Amin' : {'Wasim', 'Nick', 'Mike'},
'Wasim' : {'Imran', 'Amin'},
'Imran' : {'Wasim', 'Faras'},
'Faras' : {'Imran'},
'Mike' : {'Amin'},
'Nick' : {'Amin'}}
def DFS(graph, start, visited = None):
if visited is None:
visited = set()
visited.add(start)
print(start)
## 순회 경로
for next in graph[start] - visited:
DFS(graph, next, visited)
return visited
DFS(graph, 'Amin')
[Output]
Amin
Wasim
Imran
Faras
Mike
Nick
{'Amin', 'Faras', 'Imran', 'Mike', 'Nick', 'Wasim'}
Case 2.
[Input]
graph = {
'Amin' : {'Wasim', 'Nick', 'Mike'},
'Wasim' : {'Imran', 'Amin'},
'Imran' : {'Wasim', 'Faras'},
'Faras' : {'Imran'},
'Mike' : {'Amin'},
'Nick' : {'Amin'}}
def DFS(graph, Start):
visited = []
stack = [Start]
while stack:
n = stack.pop()
if n not in visited:
visited.append(n)
if n in graph:
temp = list(set(graph[n]) - set(visited))
temp.sort(reverse=True)
stack += temp
return " ".join(str(i) for i in visited)
DFS(graph, "Amin")
[Output]
Amin Mike Nick Wasim Imran Faras
Reference
book: 프로그래머가 알아야 할 알고리즘 40 (임란 아마드 지음, 황준식 옮김)
댓글 남기기