Dasol Hong

I am a master’s student advised by Professor Hyun Myung at KAIST (Urban Robotics Lab).

[ALGO] Lect4. 그래프 탐색 알고리즘: DFS, BFS

2 minutes to read

강의 정보
강의명: [집콕]인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고
교수: 성균관대학교 소프트웨어학과 허재필 교수님
사이트: http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/course/



image-20210814144512492

이번 시간에는 주어진 그래프에서 노드를 순회(traversal)하는 방법에 대해 배운다.


1. 그래프 탐색: DFS와 BFS

Graph Traversal(Search), 그래프 순회

그래프 순회란, 그래프의 각 vertex 하나씩 방문하는 것을 말한다. 대표적인 그래프 순회 방식은 아래와 같이 크게 두 가지로 나눌 수 있다.

  1. Breadth-First Search, BFS: 너비 우선 순회

    image-20210804162950665

  2. Depth-First Search, DFS: 깊이 우선 순회

    image-20210804163515713

BFS와 DFS은 유사한 알고리즘을 공유하지만 BFS는 queue을, DFS는 stack를 사용하여 알고리즘이 구현된다는 점에서 차이가 있다.


대략적인 알고리즘 요약

  1. 하나의 vertex를 선택한 뒤, visit이라 표시하고 queue(혹은 stack)에 삽입한다.
  2. queue(혹은 stack)이 빌 때까지 아래 동작을 반복한다.
    • queue(혹은 stack)에서 하나의 vertex를 꺼낸다.
    • 꺼낸 vertex와 인접한 vertex 중, visit이라 표시되지 않은 vertex를 queue(혹은 stack)에 삽입한다.
이때, queue(혹은 stack)이 비었는데 not visited 상태인 vertex가 존재한다면, 해당 그래프는 unconnnected graph라고 판별할 수 있다.


BFS 알고리즘

아래 예시를 통해 BFS 알고리즘을 살펴본다.

image-20210804170717830

최종 순회 순서: A-B-C-E-D-F-G-H-I


BFS 알고리즘은 Queue를 이용하여 visited vertices를 push & pop한다. (그래프를 tree구조로 해석했을 때) FIFO 성질에 의해 같은 부모를 공유하는 sibling 순서대로 순회함을 알 수 있다. 이러한 논리에 따라 BFS 알고리즘을 구현할 수 있다.


DFS 알고리즘

BFS 알고리즘이 queue를 사용하여 FIFO 순서로 그래프를 순회하였다면, DFS 알고리즘은 stack을 사용하여 LIFO 순서로 그래프를 순회한다.

아래 예시를 통해 DFS 알고리즘을 살펴보자.

image-20210804172421604

최종 순회 순서: A-B-D-C-F-E-G-H-I


DFS 알고리즘은 Stack를 이용하여 visited vertices를 push & pop한다. (그래프를 tree구조로 해석했을 때) LIFO 성질에 의해 자식 vertex를 향해 깊어지는 방향으로 순회함을 알 수 있다. 이러한 논리에 따라 DFS 알고리즘을 구현할 수 있다.


BFS와 DFS

특징

BFS와 DFS는 인접 vertex를 삽입하는 순서에 따라 최종 순회 순서가 달라진다. 즉, ordering은 unique하지 않다는 특징이 있다.


응용

BFS 혹은 DFS 알고리즘을 이용하여 그래프로부터 connected component를 구할 수 있다. "box가 비었음에도 불구하고 visited 마크되지 않은 vertex가 존재한다면, 해당 그래프는 unconnected graph라는 특성"을 이용하면 된다.



2. 그래프 탐색의 STL 활용 구현

image-20210812163243171

위와 같은 그래프를 BFS와 DFS 알고리즘을 이용하여 정렬하는 코드를 작성해보자.


BFS 및 DFS 구현


실행 결과

$ ./main.exe graph.txt 
[Graph/Init] start
# of vertices=13, # of edges = 12
... edges[A] : B
... edges[A] : H
... edges[B] : C
... edges[B] : E
... edges[C] : D
... edges[E] : F
... edges[E] : G
... edges[H] : I
... edges[H] : M
... edges[I] : J
... edges[I] : K
... edges[I] : L
[Graph/Init] end

[BFS] start
--- The result of Breadth-First Searching ---
A B H C E I M D F G J K L
[BFS] end

[DFS] start
--- The result of Depth-First Searching ---
A B C D E F G H I J K L M
[DFS] end



References

  1. [집콕]인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고-비선형 자료구조, K-MOOC: http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/courseware/1158909c057347478d7386a2b7e97214/e9d736660cad4f76bcb9a05974fe0bf2/1?activate_block_id=block-v1%3ASKKUk%2BSKKU_46%2B2021_T1%2Btype%40vertical%2Bblock%4052b62ff6da2147c9a8a65a6056681d91

참고