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

지난 번에는 그래프의 정의를 내리고 표현하는 법을 배웠다.

그래프만 잘 표현하면 뭐하나 그래프의 기능을 제대로 사용할려면

실질적으로 그래프를 잘 탐색해야 한다.

그래프의 탐색하는 방법에 대해서 알아보자.


그래프의 탐색 방법에는 크게 2가지로 나뉜다.


1.  깊이 우선탐색 (Depth First Search)

2.  넓이 우선탐색 (Breadth First Search)


많이 들어 보았을 것이다.





먼저 깊이 우선 탐색방법이다.

방식은 다음과 같다.



1. 시작되는 정점을 결정하고 방문한다. 

(시작점을 설정한다는 말이다.)




2. 시작정점에 인접된 정점중 방문되지 않는 정점을 선택

(인접한 정점중 방문하지 않는 곳으로 진행한다는 말이다.)




3. 모든 인접 정점을 스택에 저장

(시작점도 스택에 넣고 방문을 통한 모든 정점은 스택에 다 집어 넣는다는 말이다.)




4. 인접 리스트를 끝나면 스택에서 빼내어 진행

(인접한 정점이 없거나 방문했던 정점이라면 스택에서 빼주고 다음 스택으로 이동하라는 말이다.)



5. 스택이 비었을 경우 종료

(스택에서 빼주다 보면 초기 값까지 빼주고 나서 더 이상 뺄 곳이 없게 된다. 그럼 종료 하는 것이다.)




말로 설명을 죽어라 해도 이해가 안간다. 그럼 동영상 예제를 보아라

자 A B C D E F 의 정점과 간선으로 이루어진 그래프다.

깊이 우선 탐색을 할려고 한다.

그럼 스택이 필요하다 파랑색이 스택이라 생각하면 된다.




처음 시작점을 설정해보자
시작점을 A라 설정 했다. 그럼 당연히 스택에 A를 넣었다.



그 다음 A와 연결 되어 있는 간선들을 보자
B와 C 가 있다.
아무데나 간다. 나는 C 먼저 가보겠다.
(코딩할때는 자기가 편하는 방식으로 하는게 좋다.) 



왔으면 항상 스택에 집어 넣어라 C를 스택에 넣었다.
C에서 보니 연결되어 있는 간선은 A, E, D 이다.
A는 왔던곳이라 못가고 E, D 중 둘중 하나에 갈수 있다.
아무데나 간다. 나는 D를 먼저 가보겠다.


D에 왔으니 당연히 스택에 넣자.
D에서는 B, E, C로 갈수 있다.
C는 왔던곳이라 못가고 B와 E로 갈수 있다.
아무데나 간다. 나는 B부터 간다.



B에 도착했다. 도착했으니 스택에 집어 넣고
B에서 갈수있는곳은  A, D 이다.
D는 왔던곳이라 못가고
A는 가보았던 점이라 못간다.
이런... 더이상 갈 곳이 없다.
그럼 스택에서  B를 빼라
그리고 다음 스택을 가리키는 곳으로 가라


B를 스택에서 빼니 스택은 D를 가리키고 있다.
D에서 갈수 있는 곳은  B, E, C
B, C는 갔기 때문에 갈수 없다.
그러므로 E로 간다.

E 로 왔다. E를 스택에 집어 넣고
갈수 있는곳을 찾으니 C, D, F
C, D 는 갔기 때문에 갈수 없다.
그럼로 F로 간다.

F 에 왔다. 스택에 집어 넣고
F에서 갈수 있는곳이 없다.
스택에서 빼라.


다음스택이 가리키는
E
역시 갈곳이 없다. 스택에서 빼라



다음스택이 가리키는
D
역시 갈곳이 없다. 스택에서 빼라


다음스택이 가리키는
C
역시 갈곳이 없다. 스택에서 빼라


다음스택이 가리키는
A
역시 갈곳이 없다. 스택에서 빼라


스택이 완전히 비었다.(그럼 종료)

자 이제 경로가 완성된것이다.


 이게 깊이 우선탐색이다.





다음은 넓이 우선탐색 방법이다.


1. 시작되는 정점을 결정하고 방문

(시작점을 설정한다.)




2. 시작정점에 인접된 모든 정점들을 선택

(정점과 인접된 모든 정점을 찾는다.)




3. 모든 인접 정점을 큐에 저장

(위에서 연결된 모든 정점들을 전부 큐에 넣는다.)




4. 인접 리스트를 끝나면 큐에서 빼내어 진행

(인접이 없으면 큐에서 꺼낸다.)




5. 큐가 비었을 경우 종료

(큐에 정점이 없으면 종료가 되는것이다.)




이거 역시 동영상을 보고 싶게 이해하자


시작점을 A로 설정하였다.

설정과 동시에 큐에 A를 집어 넣어라

그리고 A와 인접하고 있는 정점들을 찾아라
B, C  가있다.

인접한 거 B, C 모두 큐에 집어 넣어라
나는 B먼저 넣고 C를 넣었다.
(순서는 상관없다. 코딩할때 알아서 할것)

더 이상 인접이 없는 A는 큐에서 빼내어라.

다음 큐가 B를 가리키고 있다.



자 이제 B에서 시작이다.

B와 인접된 모두 A, D를 큐에 집어넣어라
A는 아까 했기때문에 빼고 D를 집어넣었다.

더 이상 인접이 없는 B 큐에서 빼어라

다음 큐는 C를 가리킨다.



자 이제 C에서 시작

C와 인접한 A, E, D
A는 아까 했기에 빼고

D와 E를 순서로 큐에 넣었다.

더 이상 인접이 없는 C는 큐에서 빼고

다음 큐는 D를 가리킨다.



자 이제 D에서 시작

D와 인접은 B, C, E
모두 지나던 곳이다.
(여기서 그림이 잘못됬다. 글로 이해하시길)

인접이 없기 때문에 D를 큐에서 빼고

다음 큐는 E를 가리킨다.


자 이제 E에서 시작

E와 인접인 C, D, F
왓던곳 빼고는 F 만 큐에 집어 넣는다.

인접이 없기 때문에 E를 큐에서 빼고

다음 큐는 F를 가리킨다.


자 이제 F에서 시작
왔던곳 빼고 더이상 인접이 없다.
인접이 없으니 큐에서 F를 뺀다.

오잉 더이상 큐가 없네

그럼 종료이다.

이게 넓이 우선탐색이다.



이해가 갔다면 리플하나 남겨주는 센스