[알고리즘] BFS와 DFS란?

Posted on | In
탐색 알고리즘인 BFS와 DFS에 대한 이해와 소스 코드 구현. 기본적인 스택, 재귀, 트리, 그래프 등을 연관지어 이해

BFS & DFS

  • BFS, DFS는 BFT(Breadth-first traversal), DFT(Depth-first traversal)이라고도 불리는데, traversal은 트리에서 배웠던 순회와 같은 용어다.
    • 순회는 트리와 그래프 같은 연결 구조에서 노드를 방문하는데 사용된다.
    • BFS와 DFS는 순회(방문)하면서 탐색하는 탐색 알고리즘이다.
      • 단, 출발지 노드와 그래프/트리 구조에 따라 탐색하는 순서와 노드가 달라질 수 있다.

BFS(Breadth-first Search): 너비 우선 탐색

image

  • 위 그림을 봤을 때, BFS는 큐의 개념이 사용된다.
    • 노드 ‘S’ 부터 저장되고 사용된다.(FIFO)
    • 순서: S-1-2-3-4-5-6-7

BFS의 활용

  • 길 찾기, 라우팅
  • BitTorrent와 같은 P2P 네트워크에서 인접 노드 찾기
  • 웹 크롤러
  • 소셜 네트워크에서 멀리 떨어진 사람 찾기
  • 그래프에서 주변 위치 찾기
  • 네트워크에서 방송
  • 그래프에서 주기 감지
  • 연결된 구성 요소 찾기
  • 몇 가지 이론적 그래프 문제 풀기

BFS 슈도 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
BFS(graph, startVert):
    for v of graph.vertexes:
        v.color = white

    startVert.color = gray
        queue.enqueue(startVert)# 시작

    while !queue.isEmpty():
        u = queue[0]  # 큐의 헤드 (S)

        # 이웃문을 체크하는 것이 핵심부분
        for v of u.neighbors:
            if v.color == white:
                v.color = gray
                queue.enqueue(v)

        queue.dequeue()# 끝
        u.color = black

슈도 코드 해석

  • 그래프의 각 노드를 보고 방문할 노드에 대해 구분한다.
    • 일단 모든 verts(정점 또는 노드)를 방문하지 않은 상태(white)이다.
  • 다음으로 시작 노드를 gray로 표시한다.
    • gray는 시작 노드의 이웃을 탐색한다.
    • 시작 노드를 큐에 넣는다.
      • 이는 while 루프에 들어가면 첫 번째 vert가 될 것임을 의미한다.
      • while 루프의 시작 부분에서 확인하는 조건은, 큐가 비어 있지 않은지 여부이다.
      • 비어 있지 않으면 큐의 첫 번째 항목을 변수에 저장한다.(u = queue[0])
        • 각 이웃의 vert에 대해 반복문을 수행한다.
        • 방문하지 않았는지(white) 확인한다.
        • 방문하지 않은 경우 gray로 표시한다.(이웃을 탐색한다는 의미이다.)
      • 탐색한 현재 vert를 대기열에서 빼고(deque), 해당 vert를 black으로 표시한다.(방문한 것으로 표시)
  • 그래프의 모든 verts를 탐색할 때까지 위의 프로세스를 계속 진행
  • BFS는 큐 자료 구조를 활용하고 재귀 호출은 하지 않는다.
  • BFS는 노드가 적은 경우 최단 경로를 탐색할 때 유용하다.
  • 너비 우선적으로 노드를 탐색하는 경우, 큐를 활용하므로 노드가 많아지는 경우 메모리 저장 공간이 증가하는 단점이 있다.
  • BFS는 재귀적으로 동작하지 않는데, 인접한 노드에 대해 먼저 탐색하기 때문에 재귀적으로 재호출할 필요가 없다.
    • DFS와 개념을 비교해보면서 자세히 살펴보자.

DFS(Depth-first Search): 깊이 우선 탐색

image

  • 깊이 우선 탐색은 LIFO로써 스택의 개념을 사용한다.
    • 순서: 1-2-4-5-3
  • 깊이 우선 탐색 알고리즘은 다른 경로를 역추적하고 탐색하기 전에 가능한 그래프를 분할한다.
    • 깊이 별로 탐색을 진행하기 때문에, 내부적으로 그래프가 분할된 후 탐색을 진행한다는 것이다.
    • 위 그림에서 1-2-4-5 까지 탐색을 지행하고, 분할이 진행된 후 3을 탐색한다.
  • 백트래킹은 DFS에서 활용되는 방법인데, 쉽게 말해 노드가 있을만한 곳을 되돌아가서 모두 살펴본다는 개념이다.
  • 위의 그림처럼 DFS는 깊이 우선적으로 탐색을 진행하고, 재귀적으로 아래에서부터 탐색하지 않은 정점이 있는 지 확인하는 방법이다.

DFS의 활용

  • 가중 그래프의 최소 스패닝 트리 찾기
  • 길 찾기
  • 그래프에서주기 감지

  • 미로 문제

  • DFS는 그래프의 모든 노드를 방문하는 경우 사용된다.
    • DFS의 단점은 최단 경로를 찾지 못하고, 시간이 오래 걸릴 수 있다.

DFS 슈도 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
DFS(graph):#초기상태
    for v of graph.verts:
        v.color = white
        v.parent = null

    for v of graph.verts:
        if v.color == white:
            DFS_visit(v)

DFS_visit(v):
    v.color = gray

    for neighbor of v.adjacent_nodes:
        if neighbor.color == white:
            neighbor.parent = v  #트리, 그래프 -> 부모개념없다
            DFS_visit(neighbor) ## 역추적

    v.color = black
  • 위 슈도 코드에는 두 가지 기능이 있다.
  • 첫 번째 함수인 DFS()는 그래프를 매개 변수로 사용하고 모든 verts를 방문하지 않음(white)으로 표시한다.
    • 각 vert의 부모를 null로 설정한다.
    • 이 함수의 다음 루프는 그래프의 각 vert를 방문한다.
    • 방문하지 않은 경우, 해당 vert를 두 번째 함수 DFS_visit()에 전달한다.
  • 두 번째 함수인 DFS_visit()는 vert를 gray로 표시하여 시작한다.(탐색 과정에서)
    • 그런 다음 방문하지 않은 모든 노드(인접 노드)의 갯수만큼 반복문을 수행한다.
    • 이 루프에서 부모를 설정한 다음 DFS_visit()를 재귀적으로 호출한다.
    • 모든 이웃 탐색이 완료되면 vert를 black(방문함)으로 표시한다.

BFS와 DFS의 중간 비교

DFS 장점

  • 찾는 노드의 depth가 깊을수록 빠르다.
  • 메모리를 적게 차지한다.

BFS 장점

  • 최단 경로를 찾기 적합하다.
  • 찾는 노드가 인접한 경우 효과적이다.

DFS 단점

  • 노드가 무한한 갯수로 존재하는 경우, 무한반복에 빠진다.

BFS 단점

  • 큐를 이용해 노드를 저장하기 때문에 노드의 수가 많을수록 메모리를 많이 소비한다.

BFS & DFS 파이썬 소스 코드

BFS

1
2
3
4
5
6
7
8
9
10
11
12
def bfs(graph, start_node):
    visit, queue = [], [] # 방문했던 노드 목록을 차례대로 저장할 리스트와, 다음으로 방문할 노드의 목록을 차례대로 저장할 리스트를 만든다.

    queue.append(start_node) # 맨 처음에는 시작 노드를 큐에 넣어준다.

    while queue: # 큐의 목록이 바닥날 때까지 loop을 돌린다.
        node = queue.pop(0) # 큐의 맨 앞에 있는 노드를 꺼내온다.
        if node not in visit: # 해당 노드가 아직 방문 리스트에 없다면,
            visit.append(node) # 방문 리스트에 추가하고,
            queue.extend(graph[node]) # 해당 노드의 자식 노드를 큐에 추가한다.

    return visit

DFS

1
2
3
4
5
6
7
8
9
10
11
12
def dfs(graph, start_node):
    visit, queue = [], []

    stack.append(start_node)

    while stack:
        node = stack.pop() # 맨 마지막에 넣었던 아이템을 가져오게 되므로 stack과 동일하게 동작한다.
        if node not in visit:
            visit.append(node)
            stack.extend(graph[node])

    return visit

재귀를 이용한 DFS 구현

1
2
3
4
5
6
7
8
9
10
def dfs_recursive(graph, start, visited=[]):
    
    visited.append(start)
    
    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)
    
    return visited

참조

0%