[CS] 그래프 알고리즘 (깊이 우선 탐색, 너비 우선 탐색)

그래프 알고리즘은 그래프 자료구조에서 특정 목정을 달성하기 위해 사용되는 알고리즘입니다. 그래프는 정점과 간선으로 이루어진 네트워크 형태의 자료구조로, 다양한 상호 관계를 모델링할 수 있습니다. 그중 깊이 우선 탐색과 너비 우선 탐색에 대하여 알아보겠습니다.

1. 목차

깊이 우선 탐색 (DFS)

너비 우선 탐색 (BFS)

---

2. 깊이 우선 탐색 (DFS)

깊이 우선 탐색은 그래프를 탐색하는 알고리즘 중 하나로, 현재 정점과 연결된 간선 중 아직 방문하지 않은 정점을 재귀적으로 탐색하는 방식입니다. 깊이 우선 탐색은 스택(Stack) 자료구조를 활용하여 구현할 수 있습니다.

2.1. 탐색 과정

1. 시작 정점을 선택하고 해당 정점을 방문했다는 표시와 함께 시작 정점을 스택에 넣습니다.

2. 스택에서 값을 뽑아 정점으로 정하고 정점과 인접한 정점들 중 방문한 표시가 없는 정점을 선택합니다.

3. 선택한 정점을 방문했다는 표시를 하고 해당 정점을 스택에 넣습니다.

4. 스택이 비어질 때까지 2번과 3번을 반복합니다.

2.2. 예시 코드

      

      

      

    
    

      <bash />
    
import java.util.Stack;

class Main {
    static boolean[] visited = new boolean[7];

    // 그래프의 연결 상태를 2차원 배열로 표현
    static int[][] graph = {
            {0, 1, 1, 0, 0, 0, 0},  // 노드 0과 연결된 노드
            {1, 0, 0, 1, 1, 0, 0},  // 노드 1과 연결된 노드
            {1, 0, 0, 0, 0, 1, 0},  // 노드 2과 연결된 노드
            {0, 1, 0, 0, 0, 1, 1},  // 노드 3과 연결된 노드
            {0, 1, 0, 0, 0, 0, 1},  // 노드 4과 연결된 노드
            {0, 0, 1, 1, 0, 0, 1},  // 노드 5과 연결된 노드
            {0, 0, 0, 1, 1, 1, 0}   // 노드 6과 연결된 노드
    };

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        visited[0] = true;

        while (!stack.isEmpty()) {
            int node = stack.pop();
            System.out.print(node + " ");

            for (int i = 0; i < graph[node].length; i++) {
                if (graph[node][i] == 1 && !visited[i]) {
                    stack.push(i);
                    visited[i] = true;
                }
            }
        }
    }
}

출력 : 0 2 5 6 4 3 1

---

3. 너비 우선 탐색 (BFS)

너비 우선 탐색은 그래프를 탐색하는 알고리즘 중 하나로, 현재 정점과 인접한 모든 정점들을 우선 탐색 후, 해당 정점들과 다시 인접한 정점들을 탐색하는 방식입니다. 너비 우선 탐색은 큐(Queue) 자료구조를 활용하여 구현할 수 있습니다.

3.1. 탐색 과정

1. 시작 정점을 선택하고 해당 정점을 방문했다는 표시와 함께 시작 정점을 큐에 넣습니다.

2. 큐에서 값을 뽑아 정점으로 정하고 인접한 정점들 중 방문한 표시가 없는 정점을 선택합니다.

3. 선택한 정점을 방문했다는 표시를 하고 해당 정점을 큐에 넣습니다.

4. 큐가 비어질 때까지 2번과 3번을 반복합니다.

3.2. 예시 코드

      

      

      

    
    

      <bash />
    
import java.util.*;

class Main {
    static boolean[] visited = new boolean[7];
    static int[][] graph = {
        {0, 1, 1, 0, 0, 0, 0},
        {1, 0, 0, 1, 1, 0, 0},
        {1, 0, 0, 0, 0, 1, 0},
        {0, 1, 0, 0, 0, 1, 1},
        {0, 1, 0, 0, 0, 0, 1},
        {0, 0, 1, 1, 0, 0, 1},
        {0, 0, 0, 1, 1, 1, 0}
    };

    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        visited[0] = true;

        while (!queue.isEmpty()) {
            int nodeIndex = queue.poll();
            System.out.print(nodeIndex + " ");

            for (int i = 0; i < graph[nodeIndex].length; i++) {
                if (graph[nodeIndex][i] == 1 && !visited[i]) {
                    queue.offer(i);
                    visited[i] = true;
                }
            }
        }
    }
}

출력 : 0 1 2 3 4 5 6