깊이 우선 탐색(Depth First Search : DFS) 알고리즘 자바로 구현하기

- 깊이 우선 탐색(Depth First Search, DFS)이란?

시작점 v부터 인접한 정점 중에 방문하지 않은 정점 w를 방문하고 다시 w로부터 탐색을 시작합니다. 

그 후 어떤 정점 u를 방문하고 u에 인접한 모든 정점들을 이미 방문한 경우에는 그 전에 마지막으로 방문한 정점으로 되돌아가서 위의 과정들을 반복합니다. 모든 정점들을 방문한 후 탐색을 종료합니다. 

 

 

DFS 결과는 1->2->4->8->5->6->3->7입니다.

 

필요한 변수

- 정점의 passing여부를 나타내는 vertex 집합

- 정점의 연결 여부를 나타내는 c 집합

- 지나온 정점을 저장하는 p 집합 <List>

 

핵심

인접한 정점은 1을 기준으로 할 때 2,3이 인접해 있으나 2로 먼저 이동한다고 가정하고 문제를 풀어야 합니다.

두개의 정점이 연결되어 있을 경우 1, 아니면 0을 c 집합의 원소로 저장합니다.

재귀함수를 이용해야 하고, 각 vertex 집합에 false값이 있다면 인접한 정점을 찾는 로직이 수행됩니다. 

vertex 집합의 모든 원소가 true일 경우 정점 탐색 로직을 종료하여 재귀함수 호출을 종료합니다. 

 

출력

지나온 경로를 나타내는 집합 p의 원소들이 출력됩니다. 

 

코드

private ArrayList<Integer> dfs(){

boolean[] vertex = new boolean[9];

int[][] c = {

, , ,

, , ,

, ,

};

vertex[1] = true;

ArrayList<Integer> p = new ArrayList<Integer>();

p.add(1);

recursive(vertex, c, 1, p);

return p;

}

 

private void recursive(boolean[] vertex, int[][] c, int v, ArrayList<Integer> p){

int idx = 0;

 

while(isFalse(vertex)){

for(int i=1; i<c.length; i++){

if(c[v][i]==0)

if(c[v][i]==1 && !vertex[i]){

idx = i;

break;

}

}

if(idx==0)

else{

vertex[idx] = true;

p.add(idx);

recursive(vertex, c, idx, p);

}

}

}

 

private boolean isFalse(boolean[] vertex){

for(int i=1; i<vertex.length; i++){

if(!vertex[i])

return false;

}

 

private static void main(String[] args){

DFS dfs = new DFS();

System.out.println(dfs.dfs());

}

 

결과

 

이상으로 DFS 알고리즘을 마칩니다.

 

참고 문헌: DISCRETE MATHEMATICS 이산수학 Express - 7장 그래프 응용, DFS 알고리즘