그래프 - 깊이우선탐색 / 너비우선탐색 ( DFS / BFS )

자료 구조 - 그래프

노드와 간선으로 표현되며, 노드를 정점이라고도 한다. 그래프는 하나의 노드(정점)에서 여러 갈래의 간선을 통해 다른 노드 방문하는 탐색을 주로 이용된다. 이때 두 노드가 간선으로 연결되어 있다라고 할 수 있는데 다른 표현으로는 '두 노드가 인접하다'라고도 표현한다.

 

프로그래밍에서의  그래프 구조

그래프는 크게 2가지의 형태로 표현된다.

• 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
• 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식

인접 행렬

2차원 배열에 각 노드가 연결된 형태로 기록하는 방식으로, 연결되지 않은 노드끼리는 무한한 값으로 초기화 한다.

인접 리스트

메모리 측면에서 보면 인접 행렬 방식은 모든 관계를 저장하기 때문에 메모리를 낭비하게 된다. 반면 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.

그러나 데이터의 접근 속도 측면에서 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.

DFS - Depth-First Search

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

DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

BFS - Breadth First Search

너비 우선 탐색이라고 하며, 이는 가까운 노드부터 탐색하는 알고리즘이다.

BFS는 큐의 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 ㅇ낳은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 방복한다.