아래 1부터 7 까지의 노드들이 있다.
이런 노드들을 연결해놓은 아래와 같은 그림을 그래프라고한다. 트리와 그래프의 차이는 트리는 한 노드에서 또다른 노드까지 가는 방법이 1가지인데 반해 그래프는 여러가지방법이 있을 수 있다.
이제 깊이 우선 탐색을 알아보겠는데 깊이란 시작점에서 부채모양으로 퍼진형태가아닌 선형태로 탐색을 하는 것을말한다.
그림에서 1-2-4-7 , 1-2-5-6 이런식으로 탐색해 나가는것이 깊이 우선 탐색이라고 한다.
너비우선탐색은 (1-2 ,1-3) (2-4,2-5) 이런식으로 시작점을 정하면 부채꼴모양으로 가능한 연결수를 다 찾아낸후 다음 탐색을 하는 형태이다.
깊이우선탐색은 시작정점의 변경이 한번의 이동에 한번씩 된다. 하지만 너비우선탐색은 시작정점이 있으면 연결된 노드를 다 탐색한 후에 그 노드들을 시작정점들로 해서 각각 아까했던 그런작업을 또 하게된다.
우선 깊이 우선탐색을 해보자. 가장 간단한 형태로 만들었다.
N은 노드의 수다. 편의를위해 배열의 0번째 행과 열의 요소는 사용하지 않는다. 없다고생각한다.
a[i][j] 는 i와 j가 간선으로 연결되어 있다는것을 의미한다. 연결되어 있으면 1로 표시한다.
탐색한 곳의 표시는 f 배열에 1을 저장한다.
탐색의 방법으로 재귀를 사용한다.
위와 같이 끊김이 없이 연결된 형태는
이런식으로 가능하지만, 연결이 끊긴경우는
seach(1), 뿐아니라 끊긴 다른부분에서 시작점을 정해줘야한다. 그부분은 for문으로 하든 직접 시작점을 정해주든 상관없다.
결과는 위와 같고 결과와 위 그래프를 비교해보자.
1을 시작점으로 하는 재귀는 7까지 가서 끝난다.
그럼 재귀가 회귀를 하게되는데 2에서 걸린다.(처음에 노드2에서 j가 4인경우까지만 루프를 돌고 seach(4)를 호출했으므로 재귀의 회귀시에 나머지 5부터N까지 루프를 돌게된다.) 나머지도 마찬가지다. 그럼 2에서 시작점으로 하는 재귀는 6까지가고 다시 회귀하면서 2에서 시작하는 재귀는 끝나게된다. 처음 1에서시작한 재귀는 아직 회귀중이었으므로 회귀를 해서 1까지간다. 처음 1에서 첫번째 진입했던 재귀를 2에서 멈춘상태다. 재귀가 회귀한후 나머지루프를 돈다.(3을 찾는다)
모든 루프를 돌아서 f배열은 f[0]을제외한 모든 요소가 1이되었다.
*재귀는 분할점령 방식을 사용하는데 위 방법도 분할점령방식으로 이해하면된다.(분할점령이란, 해결할 문제를 쪼개어 생각해도 적용되는 알고리즘이 같을 때 사용한다.) 대표적으로 하노이탑 알고리즘도 분할점령방식이다.
2014/02/26 - [알고리즘] - 하노이탑 재귀호출 알고리즘
깊이우선탐색은 여기까지하고 너비우선탐색을 살펴보자
옆그래프를 넓이우선탐색을하게되면
1->2,3
2->4,5,6
3->?
4->?
5->7
6->?
큐에 쌓이는순서는
2,3,4,5,6,7 이된다.
시작노드는 1이고 이 지점이 바뀌면 큐에 쌓이는 것도 바뀌게된다.
코드는 다음과같다.
q는 큐다.
큐에 같은레벨의 노드들이 쌓이게되면 head는 차례대로 스택을 검사해나가면서 갈수있는 길들을 파악하게된다. 이런식으로 현재노드에서 갈수 있는 위치를 모두 큐에 저장한후, 큐에 저장된 위치들로부터 똑같은 작업을 반복해 나간다..
같은레벨이란 노드의 깊이가 같다는 것을 말한다.
코드는 시작점을 4로 한것이다.
결과는 다음과같다.
i=q[head++]; 는 시작점i를 정하는데 큐에 쌓인 순서대로 빼내가면서 탐색을 한다. 탐색은 기준노드i 에서 모든 경우를 탐색한다. 그래서 갈 수 있는 곳(탐색을 안한곳 && 갈수있는노드)은 모조리 큐에 넣는다. 넣으면서 동시에 f[]배열에 방문기록을 갱신하고, 탐색했으므로 출력한다.
///아래는 이전내용
깊이우선탐색은 먼저 걸리는넘 먼저 탐색하기 탐색방법이다.
알고리즘은 재귀를 사용하고 재귀가 역으로 복귀할때는 나머지 남은 부분들을 탐색해나간다.
쉽게말해 미로를 탐색할때 먼저 보이는 구멍으로 먼저들어간다는말이다.
재귀가 역으로 회귀할때는 들어왔던 구멍으로 돌아가면서 나머지 미탐색지역을 탐색하는 방식이다.
그럼 너비우선 탐색은 멀까?
한마디로 현재 단계에서 보이는 구멍들을 다 확인하고 탐색한다는 말이다. 이경우는 재귀를 사용하지않는다.
글쎄 재귀를 사용하는법이 있을지도 모르겠지만 내머리로는 아직까지 생각해볼엄두는 안냈다.
너비우선탐색은 큐를 사용한다.
head와 tail로 플래그를 만들어논다.
head는 현재의 나의 위치 tail은 이위치에서 보이는 구멍? 정도로 해놓으면 될듯하다.
자료구조 큐를 공부했다면, 이부분은 쉽게 이해할 수 있을 것이다.
2014/03/22 - [프로그래밍/C언어] - 자료구조 큐(Queue) C언어
1에서 시작한다면 head에 1을 넣고 tail은 다음스택을 가르킨다.
좀더 쉽게 풀어쓰자.. (아직 그림이 없기때문에)
한마디로 head는 탐색의 시작정점을 가르킨다. 그리고 현재의 정점에서 갈 수 있는 구멍들이 늘어날수록 tail의 값은 늘어난다. 이런식으로 탐색하다 head와 tail의 값이 같게 될때 탐색은 끝나게된다.