이 포스팅은 kmooc의 인공지능을 위한 알고리즘과 자료구조 (성균관대학교 / 교수 허재필)를 듣고 정리했습니다.
그래프 탐색 : BFS, DFS
그래프에 있는 노드들을 방문하는 과정으로 그래프 검색이라고 표현하기도 한다.
BFS (Breadth-First search)
너비우선탐색이라고 하며 루트노드를 먼저 방문한 후 이것의 자식노드, 이 자식노드의 자식노드의 순서로 이동한다. 너비를 우선적으로 고려해 탐색하기 때문에 depth 순서대로 탐색한다.
알고리즘
- 어떤 vertex 하나를 선택한 후 방문했다고 체크, 큐에 push한다.
- 큐가 비어있지 않을 때까지 반복한다.
- 매 반복마다 큐에서 vertex를 하나 pop하고 이 vertex를 v라고 한다.
- v 의 주위에 연결된 vertex 중 방문하지 않은 것을 방문했다고 체크, 큐에 푸쉬한다.
- 큐가 빌 때까지 수행한다.
방문하지 않은 vertex, 즉 큐에 들어간 적이 없는 vertex가 존재하면 이 그래프는 connect되어있지 않다고 할 수 있다.
- 임의의 A를 첫번째 vertex로 시작한다.
- A를 큐에 push한다.
- 큐에서 front에 있는 A를 pop하고 방문했다고 체크한다.
- A와 연결된 B, C, E를 큐에 push한다.
- 큐에서 front에 있는 B를 pop하고 방문했다고 체크한다.
- B와 연결된 vertex 중 큐에 들어간 적이 없는 D를 큐에 push한다.
- 이 과정을 계속 반복하면 A-B-C-E-D-F-G-H-I순서로 그래프를 순회한다.
DFS (Depth-First search)
깊이우선탐색이라고 하며 루트노드로부터 자식노드 중 하나인 B, B에서 깊이가 늘어나는 C와 D의 순서로 이동한다.
깊이를 늘려가는 방향으로 탐색한다.
알고리즘
- 어떤 vertex 하나를 선택한 후 방문했다고 체크, 스택에 push한다.
- 스택이 비어있지 않을 때까지 반복한다.
- 매 반복마다 스택에서 vertex를 하나 pop하고 이 vertex를 v라고 한다.
- v 의 주위에 연결된 vertex 중 방문하지 않은 것을 방문했다고 체크, 스택에 푸쉬한다.
- 스택이 빌 때까지 수행한다.
- 임의의 A를 첫번째 vertex로 시작한다.
- A를 스택에 push한다.
- 스택의 top에 있는 A를 pop하고 방문했다고 체크한다.
- A와 연결된 B, C, E를 스택에 push한다.
- 스택의 top에 있는 E를 pop하고 방문했다고 체크한다.
- E와 연결된 vertex 중 스택에 들어간 적이 없는 G, H를 스택에 push한다.
- 이 과정을 계속 반복하면 A-E-H-I-G-C-F-D-B순서로 그래프를 순회한다.
위의 두 개의 알고리즘은 유니크한 순회순서를 만들지 않는다. 스택에 쌓이는 순서는 B-C-E가 아닌 B-E-C가 될 수도 있으며 다양한 경우의 수가 존재한다. 또한, 시작하는 vertex가 A가 아닌 다른 임의의 vertex가 될 수도 있다.
이 알고리즘을 활용해 어떤 그래프에서 어떤 노드가 어떤 노드와 connect 되어있는 지 등의 정보와 connected component를 구할 수 있다.