그래프(Graph)-깊이우선탐색(DFS, Depth First Search)

그래프를 순회하기위한 방법중 너비우선탐색(BFS, Breadth First Search) 은 알아봤고 이번에는 깊이우선탐색(DFS, Depth First Search)알고리즘을 살펴보자.

깊이우선탐색(DFS, Depth First Search)은 이진트리의 전위순회(pre order)과 비슷한 개념이고 재귀나 스택(Statck)를 이용하여 알고리즘을 구현할 수 있다. 

깊이우선탐색

△ [출처] https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm

 

위에서 주어진 예제에서와 같이 DFS 알고리즘은 S에서 A에서 D로 G에서 E에서 B로, F에서 마지막으로 C로 이동한다.
DFS를 스택를 이용하여 구현할 수 있다고 하였는데 코드로 직접 구현하기전에 단계별로 어떻게 구현해야할지 살펴보자.

 

DFS를 스택을 이용한 알고리즘

처음에 스택은 없는 상태이다. 우리는 가장 먼저 방문할 정점이 어떤것인지 결정해야한다. 

S를 출발점으로 시작하기로 결정하면 S를 방문노드라고 체크하고 그것을 스택에 넣는다. 
그리고 S와 인접한 노드 중 방문하지 않은것을 탐색한다.
예제에서는 3개의 노드 { A, B, C } 가 S와 인접하면서 아직 방문하지 않은 것들인데 이중 알파벳순서에 의해 A를 선택한다. 

A를 방문한 것으로 마킹하고 스택에 넣는다. 
그리고 A와 인접한 노드들 { A, D } 중 방문하지 않은 D를 선택한다. 

D를 방문한 것으로 마킹하고 스택에 넣는다. 
그리고 D와 인접한 노드들 { B, C } 중 알파벳순서에 의해 방문하지 않은 B를 선택한다. 

 

B를 방문한 것으로 마킹하고 스택에 넣는다. 
그리고 B와 인접한 노드들은 {S, D} 인데 {S, D}는 모두 방문한 것들이기 때문에 B를 스택에서 제거한다. 

이전 노드로 돌아 가기 위해 스택의 탑에 있는 노드가  방문하지 않은 인접 노드가 있는지 확인한다.
여기에서 우리는 D가 스택 맨 위에 있다는 것을 알 수 있다.

D노드로부터 인접한 노드중 유일하게 방문을 하지 않은 것은 C 이다.
이제 C를 방문한 것으로 마팅하고 스택에 넣는다.

스택의 탑에 있는 노드가  방문하지 않은 인접 노드 있으면 계속 반복하면 되고 만약 인접노드들을 모두 방문하였으면 POP하면서
스택이 모두 비워질때까지(empty) 반복하면 된다.

 

import java.util.Stack;
import java.util.function.Consumer;
 
public class DFS {
 
    private AdjListGraph graph;
 
    // 방문한적이 있는지 체크하기위한 변수
    private boolean[] marked ;
    // 출발 S 로부터 V까지 최단경로상에서 V의 직전노드(predecessor)
    private int[] edgeTo ;
    private final int s;         // source vertex
 
    public DFS(AdjListGraph graph, int s) {
        marked = new boolean[graph.V()];
        edgeTo  = new int[graph.V()];
        this.graph = graph;
        this.s = s;
 
    }
 
 
    // 스택 이용하여 dfs 를 구현한다.
    public void dfs( Consumer<Integer> consumer) {
        Stack<Integer> stack = new Stack<Integer>();
        marked[s] = true;
        stack.push(s);
 
        while(!stack.empty()) {
            int v = stack.pop();
            consumer.accept(v);
            for (int w : graph.adj(v)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    marked[w] = true;
                    stack.push(w);
                }
            }
        }
 
    }
 
    // 재귀를 이용함.
    public void dfs(int v, Consumer<Integer> consumer) {
 
        marked[v] = true;
        consumer.accept(v);
        for (int w : graph.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(w, consumer);
            }
        }
    }
 
 
    // 출발 지점부터 노드 v 까지 최단거리(path)가 있으면 true, 없으면 false
    public boolean hasPathTo(int v) {
        validateVertex(v);
        return marked[v];
    }
 
 
    // 출발지점부터 v 까지 최단거리리 정점 목록들으 리턴한다.
    public Iterable<Integer> pathTo(int v) {
        validateVertex(v);
        if (!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<Integer>();
        for (int x = v; x != s; x = edgeTo[x])
            path.push(x);
        path.push(s);
        return path;
    }
 
    private void validateVertex(int v) {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }
}
 
 
public class Main {
 
    public static void main(String[] args)  {
        AdjListGraph graph = new AdjListGraph(9);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 5);
        graph.addEdge(3, 7);
        graph.addEdge(3, 8);
        graph.addEdge(5, 6);
        graph.addEdge(7, 8);
 
 
        DFS dfs = new DFS(graph, 1);
        // 1 2 4 5 3 7 8 6
        dfs.dfs(1 ,(i) -> System.out.print(i + " "));
        System.out.println("-----");
 
        // 7 3 5 2 1
        for(int i : dfs.pathTo(7)) {
            System.out.print(i + " ");
        }
 
    }
    
}