깊이 우선 탐색
깊이우선탐색이란 트리 및 그래프 등을 탐색하는 알고리즘이다.
특정 노드를 출발하여 깊게 들어 갈 수 있을때 까지 들어가고 들어 갈 곳이 없다면 다시 나오는 알고리즘이다.
깊게 들어간다해서 깊이 우선 탐색, 스택을 이용하여 구현한다.
위에 노드를 한번 보자.
만약 루트가 1이라면
1->2로
2->4로 4에선 더이상 갈곳이 없어 다시 나온다. 그럼 다시
3->5 5역시 갈곳이 없기에 나온다.
3->6 6도 마찬가지다.
3->7로 가고 끝난다.
그전에 알아두어야 할 것이 있는데 바로 인접행렬이다.
인접행렬이란 그래프 이론에서 인접행렬은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각행렬이다. -위키피디아 출처
바로 저거다.
예를들어
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| 1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
| 2 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
| 3 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
| 4 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
| 5 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
| 6 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
| 7 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
이런 형태가 되는게 인접행렬이다.
(1,2)(2,1) (1,3)(3,1) ... 이런 것들이 한쌍이 되는거다.
그럼 코드를 보자.
static int[] search = new int[10];
static int[][] DFS = {
{0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0},
{0,1,0,0,1,0,0,0},
{0,1,0,0,0,1,1,1},
{0,0,1,0,0,0,0,0},
{0,0,0,1,0,0,0,0},
{0,0,0,1,0,0,0,0},
{0,0,0,1,0,0,0,0},
};
search는 방문한경우 다시 방문하는 걸 막기위함이다.
public static void DFS(int v) {
//정점을 방문했다고 표시
search[v] = 1;
for (int i = 1; i <= 7; i++) {
//정점을 방문하지 않고 인접행렬이라면
if (search[i] != 1 && DFS[v][i] == 1 ) {
System.out.println(v + "에서 " + i + "로 이동!");
DFS(i);
}
}
}
함수를 호출하면 방문했다고 표시를 하고 정점을 조사해야 된다.
그리고 방문하지 않고 인접행렬이라면 이동하면 된다.
재귀로 만든 이유는 스택구조로 만들기 위해서다.
만약 더이상갈점이 없다면 다시 돌아가야하기 때문이다.
그럼 결과는 다음과 같이 나올 것이다.
1에서 2로 이동!
2에서 4로 이동!
1에서 3로 이동!
3에서 5로 이동!
3에서 6로 이동!
3에서 7로 이동!