Depth First Search

1. Problem

- root에 대하여 깊이 우선 탐색을 실행해보자.

- 깊이 우선 탐색은 너비보다 깊이를 우선적으로 탐색하는 알고리즘이다.

- 탐색 결과는 root에서 최하단까지 갔다가 다시 root에서 다른 최하단까지 가는 형식으로 나온다.

- 주로 스택으로 구현한다.

 

2. Input

1) int[][] graph

- 노드 간의 연결성 표현

2) int root

- root 노드의 값

 

3. Output

1) root에 대하여 깊이 우선 탐색을 실행한 결과

 

4. Example

// 예시: 위 그래프가 주어졌을 때, 1부터 차례대로 방문한다.
// 한 번 방문한 노드는 다시 방문하지 않는다.                      list		stack
// 첫 번째로, 1을 방문한다.                                  	[1]		[]
// 1과 연결 되어 있는 노드 중 방문하지 않은 노드를 스택에 넣는다.	[1]		[2,3]
// 스택에서 3을 꺼낸다.                                      	[1,3]		[2]
// 3과 연결 되어 있는 노드 중 방문하지 않은 노드를 스택에 넣는다.	[1,3]		[2,6]
// 스택에서 6을 꺼낸다.                                      	[1,3,6]		[2]
// 6과 연결 되어 있는 노드 중 방문하지 않은 노드를 스택에 넣는다.	[1,3,6]		[2]
// 스택에서 2를 꺼낸다.                                      	[1,3,6,2]	[]
// 2와 연결 되어 있는 노드 중 방문하지 않은 노드를 스택에 넣는다.	[1,3,6,2]	[4]
// 스택에서 4를 꺼낸다.                                      	[1,3,6,2,4]	[]
// 4와 연결 되어 있는 노드 중 방문하지 않은 노드를 스택에 넣는다.	[1,3,6,2,4]	[5]
// 스택에서 5를 꺼낸다.                                      	[1,3,6,2,4,5]	[]
// 5와 연결 되어 있는 노드 중 방문하지 않은 노드를 스택에 넣는다. 	[1,3,6,2,4,5]	[]
// 스택이 비어있게 되면 탐색을 종료한다.                       	[1,3,6,2,4,5]
// 같은 그래프에 대한 너비 우선 탐색의 결과                    	[1,2,3,4,6,5]

 

5. Code

// 위 그래프를 2차원 배열로 표현
// graph[i][j] == 1 if (i+1)과 (j+1)이 직접 연결되어 있다면
//             == 0 if 자기 자신이라면
//             == -1 if (i+1)과 (j+1)이 직접 연결되어 있지 않다면
int[][] graph = {{0,1,1,-1,-1,-1},{1,0,1,1,-1,-1},{1,1,0,-1,-1,1},
                 {-1,1,-1,0,1,-1},{-1,-1,-1,1,0,-1},{-1,-1,1,-1,-1,0}};
boolean[] visited = new boolean[graph.length];
Stack<Integer> s = new Stack<>();
s.add(1); // root = 1
visited[0] = true;
while(!s.empty()) {
    int n = s.pop();
    System.out.print(n+",");
    for(int i=0 ; i<graph[n-1].length ; i++)
        if(graph[n-1][i]==1 && !visited[i]) {
            s.push(i+1);
            visited[i] = true;
        }
}
// 출력 결과: 1,3,6,2,4,5,