[알고리즘] BFS & DFS

1. DFS(Depth-First Search, 깊이 우선 탐색)

: 최대한 깊이 내려간 뒤, 더 이상 갈 곳이 없을 경우 옆으로 이동

• 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 모든 노드를 방문하거나 경로의 특징을 저장해야 하는 문제에 사용
• BFS 보다 간단하지만 검색 속도는 느림
• 검색 대상 그래프가 클 때 유용
• 스택 또는 재귀함수로 구현

 

2 . BFS(Breadth-First Search, 너비 우선 탐색)

: 최대한 넓게 이동한 뒤, 더 이상 갈 곳이 없을 경우 아래로 이동

• 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법
• 모든 노드를 방문하거나 주로 최단 경로를 찾는 문제에 사용
• 검색 대상 그래프가 크지 않고 검색 시작 지점에서 타겟이 멀지 않을 때 유용
• 큐를 이용하여 구현

출처 https://its-blog.tistory.com/130

 

3. DFS & BFS Java 코드

3.1 DFS 알고리즘

재귀함수 사용

/* 인접 리스트 이용 */
class Graph {
    private int V;
    private LinkedList<Integer> adj[];
    
    Graph(int v) { 
    	V = v;
        adj = new LinkedList[v]; // 인접 리스트 초기화
        for (int i=0; i<v; ++i)
           adj[i] = new LinkedList();
    }
    
    void addEdge(int v, int w) {
        adj[v].add(w);
    }
    
    /* DFS */
    void DFS(int v) {
    	boolean visited[] = new boolean[V]; // v를 시작 노드로 DFSUtil 재귀 호출
        DFSUtil(v, visited);
    }
    
    /* DFS에 의해 사용되는 함수 */
    void DFSUtil(int v, boolean visited[]) { // 현재 노드를 방문한 것으로 표시하고 값을 출력
    	visited[v] = true;
        System.out.print(v + " "); // 방문한 노드와 인접한 모든 노드를 가져온다.
        Iterator<Integer> it = adj[v].listIterator();
        
        // 방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출
        while (it.hasNext()) {
            int n = it.next();
            if (!visited[n])
            	DFSUtil(n, visited); 
      	}
    }
}

스택 사용

/* 스택 이용 */
static void DFS(int s) {
    boolean visited[] = new boolean[V];
    Stack<Integer> stack = new Stack<>(); 
    visited[s] = true;
    stack.push(s);

    while (!stack.isEmpty()) {
    	s = stack.peek();
        System.out.print(s + " ");
        Iterator<Integer> i = adj[s].listIterator();
        
        // 방문하지 않은 노드면 방문한 것으로 표시하고 스택에 삽입
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n]) {
            	visited[n] = true;
                stack.push(n);
                DFS(n);
            }
        }
    }
}
    

 

3.2 BFS 알고리즘

class Graph {
    private int V;
    private LinkedList<Integer> adj[];
    
    Graph(int v) {
    	V = v; 
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
        	adj[i] = new LinkedList();
    }
	
    void addEdge(int v, int w) {
    	adj[v].add(w);
    }
    
    /* BFS */
    void BFS(int s) {
    	boolean visited[] = new boolean[V]; //방문여부 확인용 변수
        LinkedList<Integer> queue = new LinkedList<Integer>(); // Queue의 인터페이스 구현체인 LinkedList 사용
        visited[s] = true;
        queue.add(s);
        
        while (queue.size() != 0) { // 방문한 노드를 큐에서 추출(dequeue)하고 값을 출력
            s = queue.poll();
            System.out.print(s + " "); // 방문한 노드와 인접한 모든 노드를 가져온다.
            Iterator<Integer> i = adj[s].listIterator();
            
            // 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입(enqueue)
            while (i.hasNext()) {
            	int n = i.next(); 
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                } 
            } 
     	} 
    } 
}

 

참고 devuna.tistory.com/32