[자료구조] 그래프 1 (깊이 우선 탐색, 넓이 우선 탐색)

그래프에 대해 간단히 찍먹하는 느낌으로 알아보자.

먼저, 그래프를 공부하는데 정점과 간선에 대해 알아야 한다.

그림을 보면 알겠지만 정점은 노드 자체를 가리키고,

간선은 노드를 잇는 선을 간선 이라고 한다. 

 

예를 들면 

출처 : doopedia.co.kr

 

위 그림은 일명 다리 문제라고 불리는데,

여기서 A,B,C,D 는 정점이라 푸를 수 있고, 그 점들을 잇는 선을 간선이라 부를수 있다.

 

 

다음으론 방향 그래프와 무방향 그래프이다. 

먼저 방향 그래프는 정점과 간선 사이에 방향을 표시해 놓은 그래프이고

무방향 그래프는 정점과 간선 사이를 그냥 연결만 되어 있다고 생각하면 된다.

 

표현 방법은 아래와 같다.

 

무방향 그래프 

V(G1) = {0, 1, 2, 3}

E(G1) = { (0,1), (0,3), (1,3), (2,3)}

 

방향 그래프

V(G1) = {0,1,2,3}

E(G1) = { <0,1> , <0,3> , <3,1> , <2,3> } 

 

 

다음으로는 정점의 차수를 구하는 방법이다. 

먼저, 정점의 차수란 간선에 의해 연결된 정점의 수 이다.

이해를 돕기 위해 그림을 보여주고 넘어가겠다.

또한, 각 정점의 차수의 합은 간선의 개수의 2배와 동일하다.

 

 

다음으로는 단순 경로이다. 

단순 경로는 경로 중, 반복되는 간선이 없는 경우이다.

이것도 그림으로 보면 이해가 갈 것 이다. 

 

다음은 연결 그래프와 완전 그래프에 대한 개념을  알아보자.

먼저 연결 그래프이다.

연결 그래프는 모든 정점쌍에 대해 항상 경로가 존재하는 그래프이다. 

 

그에비해 완전 그래프는

그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프이다.

 

앞서 간단하게 그래프에 대해 알아보았으니, 오늘의 목표인 깊이 우선 탐색(DFS), 과 넓이 우선 탐색(BFS) 를 알아보자.

 

먼저 깊이 우선 탐색(DFS) 이다. 

깊이 우선 탐색은 최대한 깊숙히 내려간 후, 더이상 갈 곳이 없을 경우 옆으로 이동하는 방식이다. 

 

출처 https://developer-mac.tistory.com/64

깊이 우선 탐색의 개념은 루트 노드나 부모 노드에서 시작해 다음 분기로 넘어가기 전에, 

해당 분기를 완벽하게 탐색하는 방식이다. 

즉, 한 분기만을 완벽하게 찾고, 만약 찾고자 하는 값이 없을 시, 바로 다음 분기의 자료들을 검색하는 방법이다.

깊이 우선 탐색은 스택, 혹은 재귀함수로 구현한다.

 

다음으론 너비 우선 탐색이다.

너비 우선 탐색은 최대한 넓게 이동하고, 더 이상 갈 수 없을 때 아래로 이동한다. 

출처 https://developer-mac.tistory.com/64

너비 우선 탐색은 루트 노드나 부모 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법이다.

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 사용한다.

넓이 우선 탐색은 큐를 이용해 구현한다.

 

예를 들면 특정 값을 찾고자 할 때, 먼저 존재하는 노드들을 전체 검색하는 방식이다.

 

깊이 우선 탐색과 넓이 우선 탐색의 시간복잡도는 모든 노드를 검색한다는 전제 하에 동일하다.

하지만 인접 리스트와 인접 행렬을 사용하는데 차이가 있다.

 

N : 노드

E : 간선

인접 리스트 : O(N+E)
인접 행렬 : O(N²)

위와 같이 표현할 수 있다.