[java] 그래프 순회 알고리즘

04 Dec 2023

java

그래프는 정점들의 집합과 이를 연결하는 간선들로 구성된 자료구조입니다. 그래프 순회 알고리즘은 그래프의 모든 정점을 방문하는 방법을 의미합니다. 이번 블로그 포스트에서는 대표적인 두 가지 그래프 순회 알고리즘인 깊이 우선 탐색(Depth First Search, DFS)과 너비 우선 탐색(Breadth First Search, BFS)에 대해 알아보겠습니다.

깊이 우선 탐색 (DFS)

깊이 우선 탐색은 그래프의 한 정점에서 시작하여 다음 분기로 나아갈 때까지 최대한 깊숙이 탐색하는 방법입니다. 스택 자료구조를 사용하여 구현할 수 있습니다. 다음은 DFS의 동작 방식을 보여주는 예제 코드입니다.

public void DFS(Node start) {
    Stack<Node> stack = new Stack<>();

    stack.push(start);
    start.visited = true;

    while (!stack.isEmpty()) {
        Node current = stack.pop();
        processNode(current);

        for (Node neighbor : current.getNeighbors()) {
            if (!neighbor.visited) {
                stack.push(neighbor);
                neighbor.visited = true;
            }
        }
    }
}

public void processNode(Node node) {
    System.out.println(node.value);
}

위의 예제 코드는 각 정점에 방문할 때마다 processNode 메소드를 호출하여 해당 정점의 값을 출력합니다.

너비 우선 탐색 (BFS)

너비 우선 탐색은 그래프의 한 정점에서 시작하여 인접한 모든 정점을 우선으로 탐색하는 방법입니다. 큐 자료구조를 사용하여 구현할 수 있습니다. 다음은 BFS의 동작 방식을 보여주는 예제 코드입니다.

public void BFS(Node start) {
    Queue<Node> queue = new LinkedList<>();

    queue.offer(start);
    start.visited = true;

    while (!queue.isEmpty()) {
        Node current = queue.poll();
        processNode(current);

        for (Node neighbor : current.getNeighbors()) {
            if (!neighbor.visited) {
                queue.offer(neighbor);
                neighbor.visited = true;
            }
        }
    }
}

public void processNode(Node node) {
    System.out.println(node.value);
}

위의 예제 코드는 각 정점에 방문할 때마다 processNode 메소드를 호출하여 해당 정점의 값을 출력합니다.

마무리

그래프 순회 알고리즘은 다양한 문제 해결에 활용될 수 있는 중요한 알고리즘입니다. 깊이 우선 탐색과 너비 우선 탐색을 잘 이해하고 활용할 수 있다면 다양한 그래프 문제를 효과적으로 해결할 수 있을 것입니다.

깊이 우선 탐색 (DFS)

너비 우선 탐색 (BFS)

마무리

참고 자료