알고리즘

그래프 탐색 방법, 예시(DFS, BFS)

덜 무서운 지박령 2024. 1. 25. 10:00

그래프를 순회하는 방법에는 여러가지가 있지만 대표적으로 깊이우선탐색과 너비우선탐색이 존재한다.

 

1. 깊이 우선 탐색 (DFS)

어느 한 지점에서 시작하여 최대한 깊숙히 들어가서 확인한뒤 다른 루트를 확인하는 방식으로 다른 길이 발견되면 길이 있다라는 점만 기억한뒤 나중에 방문한다.

재귀호출을 사용하여 구현하거나 스택을 이용할 수 있다.

  • 장점
    그래프에서 사이클이 있는지 판단할 수 있다.
    현재 경로의 노드만 기억하므로 저장 공간의 부담이 적다.
  • 단점
    스택 오버플로우를 조심해야한다.
    단순한 검색 속도는 BFS에 비해 느리다.

예시1)

이와 같은 그래프가 있을때, A부터 시작하여 알파벳 순서를 기준으로 탐색한다고 가정한다.

처음 A을 방문하고 A와 연결되어있는 노드 중 알파벳 순서가 빠른 B를 방문한다.

이후 같은 방식으로 B와 연결되어 있는 노드 중 알파벳 순서가 빠른 C를 방문하며

그 다음으로 D,E를 탐색한다.

E까지 방문한 이후 E와 연결된 노드 중 더이상 탐색하지 않은 노드가 없으므로 다시 D로 돌아가 다른 길이 있는지 탐색한다.

현재 예시에는 다른 노드가 없으므로 A까지 backtracking되며 탐색을 종료한다.

전체 탐색 순서는 A-B-C-D-E가 된다.

 

예시2)

예시1과 유사한 위와같은 그래프를 DFS방식으로 탐색하면 A-B-C까지는 동일하지만,

C에서 더이상 인접한 노드가 없으므로 B로 돌아가 탐색을 진행하게 된다.

따라서 탐색하는 노드의 순서는 A-B-C-D-E로 동일 하지만 과정이 약간 달라진다.

 

 

 

2. 너비 우선 탐색 (BFS)

어느 한 지점에서 인접한 노드를 먼저 탐색하는 방법

시작하는 정점에서 가까운 정점을 먼저 방문한다.

자료구조는 큐를 이용하여 구현할 수 있으며, 방문한 노드를 잘 기억하고 있어야한다.

  • 장점
    최단경로를 찾고싶을 때 주로 사용한다.
    가까운 관계에 있는 정점부터 확인할 수 있다.
  • 단점
    재귀적인 방식으로는 구현하기 힘들다.

예시1)

DFS에서 사용한 예시를 그대로 사용한다면 처음 A에서 시작하여 그 다음으로는 A와 인접한 B,C를 순서대로 큐에 저장하여 A다음에 B를 방문하게 된다.

B에서 인접한 D를 큐에 저장하고 큐에서 꺼낸 C를 방문, 같은 방식으로 E를 저장하여 A-B-C-D-E의 순서로 방문하게 된다.

 

예시2)

노드를 연결하는 몇 개의 간선이 없어진 예시2에서는 A-B까지는 동일하지만, C를 방문했을 때, 큐에 아무것도 저장하지 못하고 D로 이동한다. 이후 E를 큐에 저장하고 E를 방문하게 된다. 큐가 비었으므로 탐색을 종료하게 된다.

 

 

 

DFS나 BFS는 그래프나 트리구조로 저장된 정보를 어떤 방식으로 하나씩 탐색할 것인지에 대한 방법으로 상황에 맞게 스택과 큐를 생각하며 구현해야한다.