DFS(깊이우선탐색) 알고리즘

DFS 장점

1. 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적음 
2. 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음
3. 구현이 너비 우선 탐색(BFS) 보다 간단함

 

DFS 단점

1. 단순 검색 속도는 너비 우선 탐색(BFS) 보다 느림 
2. 해가 없는 경우에 빠질 가능성이 있음

(사전에 임의의 깊이를 지정한 후 탐색하고, 목표 노드를 발견하지 못할 경우 다음 경로를 탐색하도록 함) 
3. 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로, 구한 해가 최단 경로가 된다는 보장이 없음

(목표에 이르는 경로가 다수인 경우 구한 해가 최적이 아닐 수 있음)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class DFS_LINKEDLIST {
	  static ArrayList<Integer>[] a;
	    static boolean[] visit;
	     
	    public static void main(String args[]) {
	 
	        Scanner sc = new Scanner(System.in);
	 
	        int n = sc.nextInt();   //정점의 수
	        int m = sc.nextInt();   //간선의 수
	        int start = sc.nextInt();//시작할 정점
	 
	        a = new ArrayList[n+1];     //인덱스 편의상 n+1를 하고, 0번째 요소는 사용하지 않음
	        visit = new boolean[n+1];   //인덱스 편의상 n+1를 하고, 0번째 요소는 사용하지 않음
	         
	        for (int i=1; i<=n; i++) {
	            a[i] = new ArrayList<Integer>();
	        }
	 
	        for (int i=0; i<m; i++) {
	            int u = sc.nextInt();   //간선으로 이어진 정점1
	            int v = sc.nextInt();   //정점1과 간선으로 이어진 정점2
	            //양뱡향일 경우 양쪽다 저장해준다.
	            a[u].add(v);
	            a[v].add(u);
	        }
	 
	       
	        dfs(start);
	         
	        
	    }
	     
	     
	    public static void dfs(int x) {
	    
	        visit[x] = true;
	        System.out.print(x + " ");
	         
	        for (int y : a[x]) {
	            if (visit[y] == false) {
	                dfs(y);
	            }
	        }
	    }
	
	
}