1. BFS와 DFS란?
대표적인 그래프 탐색 알고리즘이다
BFS는 Breadth-First Search약자로 너비 우선 탐색이며 정점들과 같은 레벨에 있는 형제 노드들을 먼저 탐색하는 방식이다.
이와 다르게 DFS는 Depth First Search의 약자로 깊이 우선 탐색이며 정점의 자식들을 먼저 탐색하는 방식이다.
BFS 알고리즘 구현
자료구조 큐를 사용한다.
각 노드에 연결된 정점의 노드들을 나타낸 표이며 KEY와 VALUE형식으로 나타낸다.
그래프는 위 이미지의 DFS를 따른다.
|
KEY |
VALUE |
||
|
a |
b |
c |
|
|
b |
a |
d |
e |
|
c |
a |
f |
g |
|
d |
b |
h |
|
|
e |
b |
i |
j |
|
f |
c |
k |
|
|
g |
c |
||
|
h |
d |
||
|
i |
e |
||
|
j |
e |
||
|
k |
f |
||
탐색을 위한 큐
|
방문한 큐 |
|||||
|
a |
|||||
최상위 노드의 a를 방문해야 하는 큐에 넣는다.
|
방문해야 하는 큐 |
|||||
|
a |
|||||
dequeue로 데이터를 빼고 방문한 큐에 a노드가 존재하는지 확인
없다면 방문한 큐에 enqueue 하며 방문해야 하는 큐에 a의 value값을 넣는다.
만약 방문한 큐에 a가 있다면 아무것도 하지 않는다.
|
방문해야 하는 큐 |
|||||
|
b |
c |
||||
b를 꺼내서 방문한 큐에 넣고 c뒤에 b의 value값을 넣는다.
이렇게 반복하면 방문한 큐는 다음과 같은 데이터를 가지고 있다.
|
방문한 큐 |
|||||
|
a |
b |
c |
d |
e |
f |
즉 너비 우선탐색 그래프가 완성되는 것을 볼 수 있다.
파이썬으로 구현
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
시간 복잡도는
Node의 수를 N 간선의 수를 E라 했을 경우
O(N+E)의 시간 복잡도를 따른다.
DFS 알고리즘 구현
DFS는 BFS와 다르게 하나의 스택과 하나의 큐로 구현이 가능하다.
need_visit을 stack으로 구현하고 나머지는 bfs와 유사하다.
스택 구조이기에 방문한 큐의 데이터가 들어온 순서를 간단히 작성하면
a -> c->g->f->k ->b ->e->j->i->d->h로 될 것이다.
파이썬으로 구현
def dfs(graph,start_node):
visited,need_visit=list(),list()
while need_visit:
node = need_visit.pop()
if(node not in visited):
visited.append(node)
need_visit.extend(graph[node])
return visited시간 복잡도는
Node의 수를 N 간선의 수를 E라 했을 경우
O(N+E)의 시간 복잡도를 따른다.
댓글