[자료구조와 알고리즘] 그래프 순회 - 깊이 우선 탐색 (dfs)

그래프 순회 (graph traversal), 그래프 탐색 (graph search)

• 하나의 정점에서 시작하여 그래프에 있는 정점을 한번씩 방문하여 처리하는 연산
• 그래프 탐색 방법에는 깊이 우선 탐색(depth first search: DFS), 너비 우선 탐색(breadth first search: BFS) 가 있다.

깊이 우선 탐색 (dfs 탐색)

1. 시작 정점 v를 결정하여 방문
2. 정점 v에 인접한 정점 중에서
   (1) 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다. 그리고 w를 v로 하여 다시 2번의 과정을 반복
   (2) 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 스택을 pop하여 받은 가장 마지막 장문 정점을 v로 하여 다시 2번 과정을 반복
3. 스택이 공백이 될 때까지 2번 과정을 반복

dfs 탐색 예시

dfs 구현 소스코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

class Graph {
    private ArrayList<ArrayList<Integer>> edges;
    private boolean[] visited;

    public Graph(int size) {
        this.edges = new ArrayList<ArrayList<Integer>>();

        for(int i=0;i<=size;i++) {
            edges.add(new ArrayList<>());
        }

        this.visited = new boolean[size];
    }

    public void addEdge(int start, int end) { // 간선 추가
        edges.get(start).add(end);
        edges.get(end).add(start);
    }

    public void printGraph() { // 그래프 출력
        for(int i=0;i<edges.size()-1;i++) {
            System.out.print("Vertex "+i+"의 인접리스트 -> ");
            for(int j=0;j<edges.get(i).size();j++) {
                System.out.print(edges.get(i).get(j)+" ");
            }
            System.out.println();
        }
    }

    public void clearVisitedArr() { // 방문 배열 초기화
        Arrays.fill(visited, false);
    } 

    public void dfs(int start) { // dfs 탐색 재귀로 구현
        visited[start] = true;

        System.out.print(start+" ");

        for(int i=0;i<edges.get(start).size();i++) {
            int next = edges.get(start).get(i);
            if(!visited[next]) {
                dfs(next);
            }
        }
    }

    public void stackDfs(int start) { // dfs 탐색 stack을 이용하여 구현
        Stack<Integer> st = new Stack<>();
        boolean flag = true;

        visited[start] = true;
        st.push(start);
        System.out.print(start+" ");
        while(!st.isEmpty()) {
            int cur = st.peek();
            flag = false;

            for(int i=0;i<edges.get(cur).size();i++) {
                int next = edges.get(cur).get(i);

                if(!visited[next]) {
                    st.push(next);
                    visited[next] = true;
                    flag = true;
                    System.out.print(next+" ");
                    break;
                }
            }

            if(!flag) {
                st.pop();
            }
        }
    }
}

public class DfsSearch {

    public static void main(String[] args) {
        Graph graph = new Graph(7);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 4);
        graph.addEdge(3, 6);
        graph.addEdge(4, 6);
        graph.addEdge(5, 6);

        graph.printGraph();

        graph.clearVisitedArr();

        System.out.print("정점 0부터 탐색: ");
        graph.dfs(0); // 결과 : 0 1 3 6 4 2 5 
        System.out.println(); 

        graph.clearVisitedArr();
        System.out.print("정점 0부터 탐색: ");
        graph.stackDfs(0); // 결과 : 0 1 3 6 4 2 5 
    }

}