[Algorithm] 탐색 알고리즘 DFS/BFS

기본 탐색 알고리즘 DFS와 BFS에 대한 기록이다.

DFS

DFS(Depth-First Search)

깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

그래프는 저번 기록에서 다뤄보았다.

[Data Structure] 그래프의 구성, 종류, 표현 (Graph)

DFS에 대한 그림 설명이다.

 

DFS는 보통 스택 자료구조를 이용한다.

[Data Sturcture] 스택, 큐, 우선순위 큐,

하지만, 스택을 이용하지 않고 재귀 함수로 쉽게 구현할 수 있다.

아래는 재귀 함수를 이용한 DFS 구현이다.

def dfs(graph,v,visited):
    visited[v]=True
    print(v,end=' ')
    for i in graph[v]:
        if visited[i]==False:
            dfs(graph,i,visited)
graph=[
    [],[2,3,8],[1,7],[4,5],[3,5],[3,4],[7],[2,6,8],[1,7]
]
visited=[False]*9
dfs(graph,1,visited)

그래프를 이전 기록에서 다뤘던 인접 배열로 구현했다.

 

BFS

Breadth First Search

너비 우선 탐색이라고도 불린다.

가까운 노드부터 탐색하는 알고리즘이다.

BFS의 그림 예시이다.

 

BFS는 큐 자료구조에 기초한다.

시간 복잡도는 O(N)으로 DFS 보다 좋은 편이다.

deque 라이브러리로 BFS를 직접 구현해보자.

 

from collections import deque
graph=[
    [],[2,3,8],[1,7],[4,5],[3,5],[3,4],[7],[2,6,8],[1,7]
]
visited=[False]*9
def bfs(graph,start,visited):
    #deque를 라이브러리를 이용해 queue 구현
    queue=deque([start])
    #방문한 정점을 True로 변경
    visited[start]=True
    #queue가 빌 때까지 반복문
    while queue:
        #해당 정점과 인접한 정점의 visited값을 모두 True로 바꿨다면 pop하면서 print
        v=queue.popleft()
        print(v,end=' ')
        #현재 다루는 정점의 이어져 있는 정점을 탐색
        for i in graph[v]:
            #만약 방문한 적 없는 정점이라면 visited값을 바꾸고, queue에 넣어준다.
            if visited[i]==False:
                queue.append(i)
                visited[i]=True

bfs(graph,1,visited)

BFS도 인접 배열로 그래프를 구현했다.