알고리즘 - 깊이 우선 탐색(DFS, Depth-First Search)

깊이 우선 탐색

루트 노드(또는 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전(branch) 해당 분기를 완벽하게 탐색하는 방법

• 미로를 탐색할 때 한 분기의 모든 갈래를 찾은 뒤 다음 분기로 넘어가는 방식과 유사

• BFS(너비 우선 탐색)에 비해 조금 더 간단하지만 단순 검색 속도는 BFS에 비해 느리다.

구현 방법

순환 호출 이용

import java.util.*;

// 인접 리스트를 이용 
class Graph {
	int node; // 노드
    LinkedList<Integer> list[]; // 인접리스트
    
    // 생성자
    Graph(int v){
         node = v;
        list = new LinkedList[v];
        for(int i=0; i<v; ++i){ // 초기화
        	list[i] = new LinkedList(); 
    }
    
    // 노드 연결
    void addEdge(int v, int w) { list[v].add(w); }
    
    // DFS 함수
    void DFSUtill(int v, boolean visited[]){
    	
        visited[v] = true; // 현재 노드는 방문으로 표시
        System.out.print(v + "");
        
        Iterator<Integer> i = list[v].listIterator();
        // 인접한 모든 노드를 가져옴
        
        while(i.hasNext()){// 인접 노드가 있을 때
        	int n = i.next();
            
            // 미방문 시 해당 노드를 시작 노드로 DFSUtil 호출
            if(!visited[n]) DFSUtil(n, visited); // 순환호출
        }
       
    }
    
    // 주어진 노드를 시작으로 DFS 탐색
    void DFS(int v){
    	boolean visited[] = new boolean[node];
        
        DFSUtil(v, visited);
        
    }
    
    
    void DFS(){
    	boolean visited[] = new boolean[node];
        
        // 비연결형 그래프는 모든 정점을 하나씩 방문
        for(int i=0; i<node; ++i{
        	if(visited[i] == false)
            	DFSUtil(i, visited);
        }
    }

}

참조

https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/