[Algorithm] 그래프 탐색(Graph Search)

그래프 탐색 : 하나의 시작점 Node에서 연결된 Node들을 모두 찾는 것

 

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

루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 

(1) DFS의 이해

• 정점(Vertex) 5에서 시작

• 정점 4 방문 => loop (5 이미 방문, 1 정점 방문 (재귀))

• 정점 1 방문 => loop (4 이미 방문, 2 정점 방문 (재귀))

• 정점 2 방문 => loop (5 이미 방문, 1 이미 방문)

• 정점 1로 돌아간다 => loop (4 이미 방문, 2 이미 방문, 5 이미 방문)

• 정점 4로 돌아간다. => loop (5 이미 방문, 1 이미 방문)
• 정점 5로 돌아간다 => loop (4 이미 방문, 2 이미 방문, 3 정점 방문 (재귀))

(2) 시간 복잡도

• 항상 모든 정점을 탐색한다 => O(V)
• 정점 X에서 갈 수 있는 곳들을 모두 방문
  • 인접 행렬 O(V), 인접 리스트 O(deg(x))

DFS 최종 시간 복잡도

• 인접 행렬 => O(V^2)
• 인접 리스트 => O(deg(1) + deg(2) + .... + deg(V)) = O(E)

(3) 구현

// x 를 갈 수 있다는 걸 알고 방문한 상태
static void dfs(int x) {
    //x 를 방문했다.
    visit[x] = true;
    
    // x에서 갈 수 있는 곳들을 모두 방문한다.
    for (int y : x에서 갈 수 있는 점들) {
        if (visit[y]) { // y를 이미 갈 수 있다는 사실을 안다면, 굳이 갈 필요 없다.
            continue;
        }
        // y에서 갈 수 있는 곳들도 확인 해보자
        dfs(y);
    }
}

 

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

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법

(1) Queue가 들고 있는 자료의 의미

• 방문이 가능한 정점들을 찾을 때, Queue에 해당 정점을 넣는다.
• Queue에 정점이 남았다 => 아직 방문 가능한 점이 남아있다. or 탐색 중이다.
• Queue가 비어있다 => 시작점에서 갈 수 있는 모든 점을 찾아냈다. or 탐색이 끝났다.

(2) BFS의 이해

• Start 정점 2에서 시작 => Queue에서 2 poll() => 정점 2와 인접하는 정점 1, 5 Queue에 추가

• Queue에서 1 poll() => 정점 1과 인접하는 정점 4 Queue에 추가 (2는 이미 visit이므로 추가 X)

• Queue에서 5 poll() => (4, 2, 3 모두 이미 visit)
• Queue에서 4 poll() => (1, 5 모두 이미 visit)

• Queue에서 3 poll() => 정점 3과 인접하는 정점 6, 7 Queue에 추가
• Queue에서 6 poll() => (3, 7 모두 이미 visit)
• Queue에서 7 poll() => (3, 6 모두 이미 visit)

(3) 시간복잡도

• 항상 모든 정점을 탐색한다 => O(V)
• 정점 X에서 갈 수 있는 곳들을 모두 방문
  • 인접 행렬 O(V), 인접 리스트 O(deg(x))

DFS 최종 시간 복잡도

• 인접 행렬 => O(V^2)
• 인접 리스트 => O(deg(1) + deg(2) + .... + deg(V)) = O(E)

(4) 구현

que.add(start), que.add(y)를 하면서 visit 처리를 해주어야 한다!!!
=> poll() 하면서 visit 처리를 하게 되면 정점들이 중복해서 Queue에 들어온다.

//start 에서 시작해서 갈 수 있는 정점들을 모두 탐색하기
static void bfs(int start) {
    Queue<Integer> que = new LinkedList<>();

    // start는 방문 가능한 점이므로 que에 넣어준다.
    que.add(start);
    visited[start] = true; // start visit 처리

    while (!que.isEmpty()) { // 더 확인할 점이 없다면 정지
        int x = que.poll();

        for (int y : x 에서 갈 수 있는 점들) {
            if (visited[y]) { // x 에서 y 를 갈 수는 있지만, 이미 탐색한 점이면 무시
                continue;
            }

            // y를 갈 수 있으니깐 que에 추가하고, visit 처리 하기
            que.add(y);
            visited[y] = true;
        }
    }
}

 

3. Example - BOJ 1260 - DFS와 BFS

(1) 문제

1260번: DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.

정점 번호는 1번부터 N번까지이다.

(2) 시간복잡도

• 인접 행렬 O(V^2)
• 인접 리스트 O(deg(x)^2) => 입력 순서대로 저장하면 작은 번호부터 보기 위해 차수의 크기만큼 탐색해야 한다.

• 만약 정렬한 경우 => O(deg(x)log(deg(x)))

<인접 행렬>

• 시간 : O(V^2)
• 공간 : O(V^2)

<인접 리스트>

• 시간 : O(E logE)
• 공간 : O(E)

(3) 구현

public class S3_1260 {
    static StringBuilder sb = new StringBuilder();
    static int N;
    static int M;
    static int V;
    static ArrayList<Integer>[] list;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String str = br.readLine();
        st = new StringTokenizer(str, " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        list = new ArrayList[N+1];
        for (int i = 1; i <=N; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i = 0; i <M; i++) {
            str = br.readLine();
            st = new StringTokenizer(str, " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }
        //정렬
        for (int i = 1; i <=N; i++) {
            Collections.sort(list[i]);
        }

        visited = new boolean[N+1];
        dfs(V);
        sb.append("\n");
        visited = new boolean[N+1];
        bfs(V);

        System.out.println(sb);
    }

    static void dfs(int x) {
        visited[x] = true;
        sb.append(x).append(" ");
        for (int y : list[x]) {
            if (visited[y]) {
                continue;
            }
            dfs(y);
        }
    }

    static void bfs(int start) {
        Queue<Integer> que = new LinkedList<>();
        que.add(start);
        visited[start] = true;
        
        while (!que.isEmpty()) {
            int x = que.poll();
            sb.append(start).append(" ");
            
            for (int y : list[x]) {
                if (visited[y]) {
                    continue;
                }

                que.add(y);
                visited[y] = true;
            }
        }
    }
}