그래프(Graph) - 깊이우선검색(DFS)??

안녕하세요~
몰아하는 숙제에 치이며 사는 테슬라입니다.

오늘은 저번 시간에 이어 양대산맥중의 하나인
깊이우선검색(DFS = Depth First Search)에 대해서 포스팅하는군요.

깊이우선검색은 너비우선검색과는 다르게 시작 정점에서 하나만 죽어라 파고 들어가는 것이지요.
더 이상 파고 들어갈게 없으면 방문하지 않았던 남은 곳에서 이어서 다시 끝까지 파고드는 것을  반복하는 것이지요.

여기서도 방문했다는 체크는 필요합니다.
하지만 저번의 너비우선검색과는 약간 다릅니다.
왜 다를까요? 이유는 담아두는 방식의 차이입니다.
너비우선검색은 큐를 사용했지요? 그렇다면 깊이우선검색은 스택을 사용합니다.
큐는 먼저 들어가면 어떻게 되도 먼저 나올 수 밖에 없기 때문에 들어갈때 체크해도 상관없지만,
스택의 경우 먼저에 들어가는것이 나중에 나오니 먼저 들어간다 하더라도 그 경우보다 나중에 스택에 쌓이면서 더 일찍 방문 될 수 있는것이지요.

자 이렇게 말하니 설명이 이상하실수도 있으니 예를 들어가면서 볼까요?

 저번에 썼던 그래프입니다.

이것도 같지요.

자 저번처럼 A부터 시작합시다.
A를 방문합니다. 방문했다고 체크해줍니다.
그리고 A에 연결된 나머지 노드들을 스택에 넣어줍니다

A의 방문을 마쳤으니 스택에서 하나 꺼내주죠.
B가 나오는군요. B를 방문했습니다. 체크~
B를 보니 A 와만 연결됬는데 A는 체크되어 있으니 넣어줄게 없네요.

다음것을 꺼내니 C가 나오네요.
C에는 A와 D가 연결되어 있네요.
A는 체크되어있으니 D를 넣어줍니다. 스택 안에 들어있어도 먼저 처리되지는 않으니 넣어주세요.

자 꺼내줍시다. D가 나오는군요. D에는 A, C, G가 연결되어 있군요.
A와 C는 이미 방문 체크되어 있으니 G를 넣어줍니다.

자, 또 스택에서 꺼냅시다. 역시 방금 넣은 G가 나오는군요.
G의 연결 노드중 E만 아직 방문가 되지 않았네요.
넣어주세요.

이제 또 꺼냅시다. 이번엔 E군요.
E에는 F만 방문하지 않았네요. 스택에 넣으면

자 스택에서 꺼내면 F가 나오네요.
F에는 E만 연결되어있는데 아까 처리됬으니 넘어가겠군요.
그럼 스택에서 꺼내봅시다. D가 나오겠지요. 하지만 D는 아까 방문했으니 넘어가고, 다음것인 E도 방문했었지요.
더이상 스택에 남은것이 없네요. 그럼 방문이 완료된 것입니다.

방문 순서는 A-> B-> C-> D-> G-> E-> F 순이군요.
그림으로 보인다면

이렇게 되겠지요?

아 그리고 말씀드릴것이 있는데 꼭 모두 스택에 담을 필요는 없습니다.
현재 정점에서 연결되어있는 방문하지 않은 정점(노드)가 두 개 이상일 때 하나만 스택에 넣어주고 다른 하나를 방문해주면 됩니다.
만약 방문 안한 정점이 하나라면 바로 거기를 방문하면 되는 것이지요.
왜일까요?
ⓞ이라는 노드에 ①과 ②라는 노드가 연결되어 있다고 칩시다.

위에 것은 모두 스택에 넣었다가 하나를 꺼내는겁니다.
밑에것은 하나는 스택에 넣고, 다른 하나를 방문하는 겁니다.
보시다시피 결국은 ①이 방문되지요?
이런식으로 모두 스택에 넣을 필요는 없지요.

그럼 왜 저는 넣었을까요...음...그냥 설명하기 편하려고...크흠...
음음 아무튼 깊이우선검색은 스택을 이용하여 사용할 수 있습니다.

자 오늘도 틀린 부분이나 오타가 있다면 꼭꼭 알려주세요!!