(자료구조) 깊이 우선 탐색(DFS) - 그래프(2)

ㅁ● 그래프 탐색이란
  - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다.

● 깊이 우선 탐색(DFS, Depth-First Search)이란 ? 
  - 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에

     해당 분기를 완벽하게 탐색하는 방법을 말한다.
ex)
   미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 

   다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
   즉, 깊게(deep) 탐색할 길을 끝까지 탐색한 후, 더이상 길이 존재하지 않으면, 가장 가까운 분기점(Branch)으로 돌아와 

     다음 탐색 위치를 탐색하는 방식이다.
  - 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

● 깊이 우선 탐색(DFS)의 특징
 - 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다. ( 재귀 구현시) 

 - 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
 - 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 

   여부를 반드시 검사 해야 한다.(그래프는 트리와 다르게 Cycle 이 존재하므로...)

 

● 깊이우선 탐색 방법

DFS 예제

 

위 그림과 같은 그래프(Graph) 가 존재할때, 최초 정점(Vertex) 로 1 부터 순회한다고 하면, 과정은 아래 설명과 같다.

 

 

  1. 1번 정점(Vertex)을 기준으로 연결된 정점은 2 ,3 ,5 이기 때문에 최초 2번 정점을 방문한다.

  2. 2번 정점 기준에서는 방문할 노드가 1밖에 없다. (하지만 1은 이미 방문된 노드) 따라서 BackTracking 한다.

  3. 1번 정점에서 다음 방문하지 않은 정점인 3으로 이동한다.

DFS 순회 1

 

 

   4. 3번 정점을 기준으로 방문하지 않은 다음 노드인 4로 이동한다.

   5. 4번 정점은 더이상 방문하지 않은 노드가 없으므로 BackTracking 하여 3으로 이동한다.

   6. 3번 정점에서 아직 방문하지 않은 노드인 5로 이동한다.

DFS 순회 2

 

    7. 5번 정점에서는 더이상 방문하지 않은 정점은 존재하지 않으므로 BackTracking 하여 3으로 돌아간다.

    8. 3번 정점으로 오면 이제 더이상 방문할 곳이 없다. BackTracking 하여, 최초 시작점으로 돌아가며 순회가 종료된다.

 

DFS 순회 3

 

● 깊이 우선 탐색의 구현

   - 깊이 우선 탐색 (DFS) 의 구현 방식은 2가지가 있다. 

       1. 명시적 Stack을 활용한 구현 방법

       2. 함수의 재귀 호출을 활용한 구현 방법

    

    해당 DFS 탐색을 구현하기 앞서, Graph 클래스의 구성은 다음과 같다.(공통 부분)

 

  ○ Graph Class

// Graph 클래스
class Graph{
    private int V;    // 멤버변수1 : 정점의 개수 
    private LinkedList<Integer> adjList[]; // 멤버변수2 : 간선의 표현 Linked List 
   
    Graph(int v){ // 생성자 , Graph의 Instance 생성 시, Graph 초기화
        V = v;
        adjList = new LinkedList[v];
        for(int i=0;i<v;i++)
        adjList[i] = new LinkedList();
    }

    void addEdge(int v,int w) { // 정점에서 정점간 간선 연결 : 정점 v 에서 정점 w로 간선 연결
        adjList[v].add(w);
    }
}

 

 ○ Main Method

    public static void main(String[] args){
    	// 1.그래프 생성 및 초기화
        Graph g = new Graph(4); 
		//2. 간선 연결
        g.addEdge(0, 1); 
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);

		//3. DFS 호출
        g.DFS(2);
        g.DFS();
        g.DFSWithStack(2);
    }

 

  ○ 명시적 Stack을 활용한 구현

   - Stack 을 활용한 구현은, Stack 에 현재 정점의 위치를 저장하는 용도로 활용한다. 

   - Stack에 저장된 정점은 다음 정점에서 더이상 방문할 정점이 없는 경우, 이전 정점으로 돌아가기 위한 저장소 역할이다.

   - Stack에 저장된 정점이 존재하지 않을 경우, 모든 정점에 대한 방문이 완료되고, 시작위치로 돌아온 것이므로 프로그램        을 종료한다.

 

    - 1.Pseudo Code 

void DFSWithStack (Graph vertex){

    let S be a stack;  // 1. 스택을 초기화

    S.push(vertex);    // 2. 시작 정점을 stack에 push

    while S is not empty do{ // 3. Stack이 Empty 되면 반복 종료

        v = S.pop() // 3. 최초 시작 정점을 Stack에 저장

        if (vertex is not labeled as visited then){  // 4. 방문되지 않은 정점인 경우,

            label v as discovered // 5. 정점을 방문 처리

            for (all edges from v to w in Graph.adjacentEdges(v) do){ // 6. 해당 정점을 기준으로 인접 정점을 차례대로 방문

                if (w is not labeled as visited then) // 7. 아직 방문되지 않은 정점으로 이동시, Stack에 현재 정점을 저장

                  S.push(w)

            }

        }

    }

}

 

    - 2.구현

    void DFSWithStack(int v){
        // Init
        boolean[] visited = new boolean[V];
        Stack<Integer> stV = new Stack<Integer>();
        //DFSHelper(v); // 현재 정점 방문 처리
        stV.push(v); // stack 에 현재 Vertex 저장
        while(!stV.empty()){ // Stack이 비어있지 않은 경우 반복
            int nextV = stV.pop();
            if(!visited[nextV]){ // 방문 처리되지 않은 경우 
                System.out.print(nextV+" ");
                visited[nextV] = true;
                for(int i=0;i<adj[nextV].size();i++){ // 해당 정점에 연결된 정점 기준으로 순차 방문
                        int nV = adjList[nextV].get(i);
                        if(!visited[i]) 
                            stV.push(i); 
                }
            }
        }
    }

 

  ○ 함수의 재귀 호출을 활용한 구현 방법

     재귀호출을 이용하면, Stack 을 활용한 코드보다 간결하게 구현이 가능하다. 

 

    - 1. Pseudo Code 

    void search(Graph vertex){

        visit(vertex); // 1. 기준 vertex 방문

        vertex.visited = true; // 1-1. 방문한 노드를 표시

        // 2. 현재 정점과 인접한 정점을 모두 방문

        for each(Node n in root.adjacent){

            if(n.visited == false){ // 4. 방문하지 않은 정점을 찾는다.

                search(n); // 3. root 노드와 인접한 정점 정점을 시작 정점으로 DFS 시작

            }

        }

    }

 

     - 2. 구현 코드

    // 재귀 호출을 통한 DFS 구현 Func
    void DFSHelper(int v,boolean visited[]){
        visited[v] = true;
        System.out.print(v + " ");

        Iterator <Integer> i = adjList[v].listIterator();
        while(i.hasNext()){
            int n = i.next();

            if(!visited[n])
                DFSHelper(n, visited);
        }
    }
// 특정 정점을 기준으로 방문 호출 (Overloading)
    void DFS(int v){
        boolean visited[] = new boolean[V];
        DFSHelper(v, visited);
        System.out.println(" ");
    }
// 최초 정점 기준으로 방문 호출 (Overloading)
    void DFS(){
        boolean visited[] = new boolean[V];
        for(int i=0;i<V;i++){
            if(visited[i]== false)  DFSHelper(i, visited);
        }
    }

 

 

● 전체 구현 코드

package DataStructure;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;

/*  pseudoCode
    // 깊이 우선 탐색의 구현
    void search(Graph vertex){
        visit(vertex); // 1. 기준 vertex 방문
        vertex.visited = true; // 1-1. 방문한 노드를 표시
        // 2. 현재 정점과 인접한 정점을 모두 방문
        for each(Node n in root.adjacent){
            if(n.visited == false){ // 4. 방문하지 않은 정점을 찾는다.
                search(n); // 3. root 노드와 인접한 정점 정점을 시작 정점으로 DFS 시작
            }
        }
    }
 */

// void DFSWithStack (Graph vertex){
//     let S be a stack;  // 1. 스택을 초기화
//     S.push(vertex);    // 2. 시작 정점을 stack에 push
//     while S is not empty do{ // 3. Stack이 Empty 되면 반복 종료
//         v = S.pop() // 3. 최초 시작 정점을 Stack에 저장
//         if (vertex is not labeled as visited then){  // 4. 방문되지 않은 정점인 경우,
//             label v as discovered // 5. 정점을 방문 처리
//             for (all edges from v to w in Graph.adjacentEdges(v) do){ // 6. 해당 정점을 기준으로 인접 정점을 차례대로 방문
//                 if (w is not labeled as visited then) // 7. 아직 방문되지 않은 정점으로 이동시, Stack에 현재 정점을 저장
//                   S.push(w)
//             }
//         }
//     }
// }
 class Graph{
    private int V;
    private LinkedList<Integer> adjList[];
   
    Graph(int v){
        V = v;
        adjList = new LinkedList[v];
        for(int i=0;i<v;i++)
        adjList[i] = new LinkedList();
    }

    void addEdge(int v,int w) {
        adjList[v].add(w);
    }

    void DFSHelper(int v,boolean visited[]){
        visited[v] = true;
        System.out.print(v + " ");

        Iterator <Integer> i = adjList[v].listIterator();
        while(i.hasNext()){
            int n = i.next();

            if(!visited[n])
                DFSHelper(n, visited);
        }
    }

    void DFS(int v){
        boolean visited[] = new boolean[V];
        DFSHelper(v, visited);
        System.out.println(" ");
    }

    void DFS(){
        boolean visited[] = new boolean[V];
        for(int i=0;i<V;i++){
            if(visited[i]== false)  DFSHelper(i, visited);
        }
    }


    // boolean DFSHelper(int v){
    //     System.out.println(v + " ");
        
    //     // first 방문
    //     if(visitdS[v] == false){
    //         visitedS[v] = TRUE;
    //         return TRUE;
    //     }
    //     // 이미 방문되었었던 vertex
    //     return FALSE;
    // }

    void DFSWithStack(int v){
        // Init
        boolean[] visited = new boolean[V];
        Stack<Integer> stV = new Stack<Integer>();
        //DFSHelper(v); // 현재 정점 방문 처리
        stV.push(v); // stack 에 현재 Vertex 저장
        while(!stV.empty()){
            int nextV = stV.pop();
            if(!visited[nextV]){
                System.out.print(nextV+" ");
                visited[nextV] = true;
                for(int i=0;i<adj[nextV].size();i++){
                        int nV = adjList[nextV].get(i);
                        if(!visited[i])
                            stV.push(i);
                }
            }
        }
    }


 }
public class Dfs {

    public static void main(String[] args){
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);

        g.DFS(2);
        g.DFS();
        g.DFSWithStack(2);
    }
   
}