[Java] DFS : 깊이 우선 탐색

DFS : 깊이 우선 탐색

개요

그래프의 모든 정점을 특정한 순서로 탐색하는 그래프의 탐색 알고리즘 중 하나이다.

 

DFS에 사용할 그래프

정점 1로부터 시작해서 모든 정점을 탐색하기 위한 목적이다.

현재 지점으로부터 인접한 지점을 찾아야 하므로 "재귀" 를 사용한다.

 

현재 방식은 단순히 "탐색" 만 할 뿐이며, D, F 등의 계산은 하지 않는다.

탐색의 우선순위는 정점의 번호가 작은 순이다.

 

파란색 정점은 방문 했다는 표시이다.

주황색 정점은 방문한 뒤 되돌아온다는 표시이다.

 

동작

최초로 1 정점을 방문한다.

정점 1에서 인접한 노드를 찾는다.

정점 2를 방문한다.

정점 2에서 인접한 노드를 찾는다.

 

정점 3을 방문한다.

정점 3에서 갈 곳이 없으므로 2로 돌아온다.

정점 4를 방문한다.

정점 4에서 인접한 노드를 찾는다.

정점 5를 방문한다.

정점 5에서 인접한 노드를 찾는다.

정점 7을 방문한다.

정점 7에서 방문할 곳이 없으므로 5로 돌아온다.

정점 8을 방문한다.

정점 8에서 갈 곳이 없으므로 5로 다시 돌아온다.

정점 5에서 갈 곳이 없으므로 4로 돌아온다.

정점 6을 방문한다.

정점 6에서 갈 곳이 없으므로 4로 돌아온다.

정점 4에서 갈 곳이 없으므로 2로 돌아온다.

정점 2에서 갈 곳이 없으므로 1로 돌아온다.

모든 노드가 탐색 되었으므로 탐색 알고리즘을 종료한다.

코드

import java.util.Vector;

public class 깊이_우선_탐색 {
    // 그래프의 인접 리스트 표현
    static Vector<Vector<Integer>> adj;
    // 각 정점을 방문했는지 여부를 나타낸다.
    static Vector<Boolean> visited;

    // 깊이 우선 탐색의 구현
    public static void dfs(int here) {
    	// here+1은 index가 0부터 시작하기 때문에 편의를 위해 1을 추가해줬다.
        System.out.println((here+1) + ": 방문");
        visited.set(here, true);

        for (int i = 0; i < adj.get(here).size(); i++) {
            int there = adj.get(here).get(i);
            // 아직 방문한 적이 없다면 방문한다
            if (!visited.get(there)) {
                dfs(there);
            }
        }
    }

    // 모든 정점을 방문한다
    public static void dfsAll() {
        // visited를 모두 false로 초기화
        for (int i = 0; i < adj.size(); i++) {
            visited.add(false);
        }

        // 모든 정점을 순회하면서, 아직 방문한 적 없으면 방문한다.
        for (int i = 0; i < adj.size(); i++) {
            if (!visited.get(i)) {
                dfs(i);
            }
        }
    }

    public static void main(String[] args) {
        adj = new Vector<>();
        visited = new Vector<>();

        for (int i = 0; i < 8; i++) {
            adj.add(new Vector<>());
        }

        adj.get(0).add(1);
        adj.get(0).add(5);
        
        adj.get(1).add(0);
        adj.get(1).add(2);
        adj.get(1).add(3);
        
        adj.get(2).add(1);

        adj.get(3).add(4);
        adj.get(3).add(5);
        adj.get(3).add(6);

        adj.get(4).add(3);
        adj.get(4).add(6);
        adj.get(4).add(7);

        adj.get(5).add(0);
        adj.get(5).add(3);

        adj.get(6).add(3);
        adj.get(6).add(4);
        
        adj.get(7).add(4);

        dfsAll();
    }
}

출력

1: 방문
2: 방문
3: 방문
4: 방문
5: 방문
7: 방문
8: 방문
6: 방문