DFS - 깊이우선 탐색 알고리즘 작성

* DFS 개념 

DFS는 그래프형태의 자료구조를 모두 방문하는 방법중 하나이다. 

* DFS (Depth first search) 알고리즘 참고 : https://coding-factory.tistory.com/611

[Algorithm] DFS 알고리즘 (Depth First Search)

그래프형태의 자료구조를 코드로 표현하는 방법에는 인접리스트 형태, 인접행렬 형태가 있다.

인접리스트 형태는 자신과 연결된 노드의 "번호"를 나열한 형태의 2차원 배열이고, 

인접행렬 형태는 모든 노드를 순서대로 나열하면서, 자신과 연결된 노드는 1로, 연결되지 않는 노드는 0으로

표현한 형태의 2차원 배열이다. 

 

* 자료구조 그래프 참고 : https://coding-factory.tistory.com/610

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?

 

* DFS 탐색 알고리즘을 재귀함수 형태로 작성

DFS탐색 알고리즘 핵심 : 

0번노드부터 시작하여 첫번째로 연결된 노드로 방문시작. 

방문한 노드는 따로 저장하여,  재방문하지 않도록 한다. 

다음 노드로 방문하면,  다시 해당노드의 첫번째 연결된 노드로 방문한다. (재귀함수호출)

재귀함수를 반복하다가 현재노드에서 더이상 방문할 노드가 없을때, 

이전 노드의 두번째 연결된 노드로 방문.  이 것을 반복하여 모든 노드방문이 완료되면 

종료된다. 

 

인접리스트로 표현한 그래프를 DFS 탐색하는 메소드와 

인접행렬로 표현한 그래프를 DFS 탐색하는 메소드를 만들어보았다.

package test;

public class dfs_test_01 {

    //방문 완료한 노드 기록용 배열 
    static int[] visited = new int[10];
	
    //인접리스트 탑색 dfs
    public static void dfs_list(int [][] graph, int start) {	
		//방문 기록 (1 : 방문)
		visited[start] = 1;
		System.out.println("방문함="+start);		
		for(int i=0; i<graph[start].length; i++) {
			int next = graph[start][i]; //start 노드의 연결노드 next			
			//next가 방문하지 않은 노드라면 next노드로 이동하여 재귀함수 호출
			if(visited[next] != 1) {
				dfs_list(graph,next);
			}
		}		
	}
	
	//인정행렬 탐색 dfs
	public static void dfs_array(int [][] graph, int start) {	
		//방문 기록 (1 : 방문)
		visited[start] = 1;
		System.out.println("방문함="+start);		
		for(int i=0; i<graph[start].length; i++) {
			//graph[start] 배열의 인덱스번호가 노드번호임.
            //graph[start][i] 요소가 1(연결)이고 i 가 방문노드가 아닐때 
			if(graph[start][i] == 1 && visited[i] != 1) {
				dfs_array(graph,i);
			}
		}		
	}
	
	public static void main(String[] args) {
       //아래 그래프를 인접리스트 형태로 표현
		/*       ↗ 3
		 *     1  
		 *   ↗  ↘ 4
		 * 0     
 		 *   ↘  ↗ 5
		 *     2
		 *       ↘ 6
		 */
		int[][] list = {{0,1,2}, {1,0,3,4}, {2,0,5,6},{3,1},{4,1},{5,2},{6,2}}; 
		dfs_list(list,0);
		//방문순서 0,1,3,4,2,5,6
		
		System.out.println("---------");
		
		//아래 그래프를 인접행렬형태로 표현
		/*         
		 *        ↗ 3
		 *      1   
		 *   ↗  
		 * 0     
 		 *   ↘   
		 *      2    
		 */
		int[][] array = {{1,1,1,0},{1,1,0,1},{1,0,1,0},{0,1,0,1}};
		dfs_array(array,0);
		//방문순서 0,1,3,2
	}
}