[알고리즘/Java]그래프와 DFS, BFS 탐색 알고리즘

  탐색 알고리즘은 입력으로 주어진 그래프를 탐색하고, 그 "구조"를 파악하는 알고리즘이다. 수많은 흥미로운 문제가 그래프로 표현 가능하기 때문에, 그래프를 탐색하고 구조를 파악하는 건 중요하다.

 

  그럼 먼저 그래프를 표현하는 방식에 대해서 알아보자.

---

 

그래프와 DFS, BFS 탐색 알고리즘

 

그래프의 표현

 

  그래프를 표현하는 방법은 대표적으로 두 가지 방식이 있다. 첫 번째는 Linked List를 이용하는 방식이고, 또 다른 방식은 인접 행렬을 이용하는 방식이다. Linked List 방식은 노드에 연결된 다른 노드들을 Linked List로 연결시킨 것이고, 인접 행렬 방식은 노드가 다른 노드에 연결되어 있는지 여부를 행렬로 표시한 것이다.

 

  따라서 자료구조를 인접행렬을 사용하여 그래프를 표시하는 것이 구현에는 간단하나, 늘 노드의 수 N의 제곱(N^2)만큼의 메모리가 필요하다. Linked List 방식은 노드에 연결된 부분만 표현하면 되기 때문에 인접 행렬 방식보다 적은 메모리를 필요로 한다.

 

어떤 그래프를 Linked List와 인접행렬로 표현하면 다음과 같다.

그래프(좌 상단)를 Linked List(우 상단)와 인접행렬(하단)으로 표현

 

DFS(Depth First Search) : 깊이 우선 탐색

 

  DFS는 이름에서 알 수 있듯, 가능한 한 더 깊이 검색한다. 한 문장으로 표현하자면 "가장 최근에 발견한 노드로부터 새로운 노드를 찾는 방식."이다. DFS는 스택으로 구현하거나, 재귀적인 방법으로 구현할 수 있다. 재귀적으로 구현하는 방법이 더 간단하지만 연산 속도나 메모리에 주의해야 한다.

 

  DFS의 동작 방식을 그림으로 표현하면 다음과 같다.

 

스택으로 표현한 DFS의 동작 순서

1. 시작점에서 아직 방문하지 않은 노드를 찾는다.

2. 방문하지 않은 노드가 있다면 Stack에 넣고 방문 표시를 한다.

3. 다음 노드로 이동한다.

4. 방문하지 않은 노드가 없다면 위로 올라간다. (Stack에서 노드를 꺼낸다.)

 

  DFS를 간단하게 자바로 구현하면 다음과 같다.

public class Dfs {
    public static void main(String[] args) {
        LinkedList[] linkedList = new LinkedList[9];
        boolean[] isVisited = new boolean[9];

        for(int i = 0; i < 9; i++){
            linkedList[i] = new LinkedList<>();
            isVisited[i] = false;
        }

        linkedList[1].add(2);
        linkedList[1].add(3);
        linkedList[1].add(8);
        linkedList[2].add(1);
        linkedList[2].add(7);
        linkedList[3].add(1);
        linkedList[3].add(4);
        linkedList[3].add(5);
        linkedList[4].add(3);
        linkedList[4].add(5);
        linkedList[5].add(3);
        linkedList[5].add(4);
        linkedList[6].add(7);
        linkedList[7].add(2);
        linkedList[7].add(6);
        linkedList[7].add(8);
        linkedList[8].add(1);
        linkedList[8].add(7);

        DepthFirstSearch(linkedList, isVisited, 1);
    }

    public static void DepthFirstSearch(LinkedList[] linkedList, boolean[] isVisited, int currentNode){
        if(!isVisited[currentNode]){
            System.out.println("currentNode = " + currentNode);
            isVisited[currentNode] = true;
        }

        for(int i = 0; i < linkedList[currentNode].size(); i++){
            int nextNode = (int)linkedList[currentNode].get(i);
            if(!isVisited[nextNode]){
                DepthFirstSearch(linkedList, isVisited, nextNode);
            }
        }
    }
}

 

  DFS는 현재 노드에서 선택된 하나의 노드를 우선 탐색하기 때문에, 그래프의 Sub 그래프를 파악하거나, 연결되지 않은 그래프를 찾아낼 때 사용 할 수 있다.

 

BFS(Breadth First Search): 너비 우선 탐색

 

  너비 우선 탐색은 많은 그래프 알고리즘의 원형이 되는 알고리즘이다. 특정 노드에서 발견할 수 있는 모든 노드를 탐색하고, 다음으로 이동한다.

 

  BFS의 동작 방식을 그림으로 표현하면 다음과 같다.

 

너비 우선 탐색의 동작 순서

1. 시작점에서 아직 방문하지 않은 노드를 모두 찾아서 방문 표시를 하고 Queue에 넣는다.

2. Queue에서 노드를 꺼내 다음 노드로 진행한다.

3. 1~2번을 반복한다.

 

  동작 방식 자체도 DFS에 비해 간단하기 때문에 보통은 BFS가 탐색시간이 조금 더 빠르다. 하지만 BFS는 특정 노드에 연결된 모든 노드를 찾기 때문에, 자식 노드의 Sub 그래프를 파악하기는 어렵다.

 

  BFS를 간단하게 자바로 구현하면 다음과 같다.

 

public class BfsUsingQueue {
    public static void main(String[] args) {
        LinkedList[] linkedLists = new LinkedList[9];

        for(int i = 0; i < 9; i++){
            linkedLists[i] = new LinkedList<>();
        }

        linkedLists[1].add(2);
        linkedLists[1].add(3);
        linkedLists[1].add(8);
        linkedLists[2].add(1);
        linkedLists[2].add(7);
        linkedLists[3].add(1);
        linkedLists[3].add(4);
        linkedLists[3].add(5);
        linkedLists[4].add(3);
        linkedLists[4].add(5);
        linkedLists[5].add(3);
        linkedLists[5].add(4);
        linkedLists[6].add(7);
        linkedLists[7].add(2);
        linkedLists[7].add(6);
        linkedLists[7].add(8);
        linkedLists[8].add(1);
        linkedLists[8].add(7);


        BreadthFirstSearch(linkedLists);
    }

    public static void BreadthFirstSearch(LinkedList[] linkedList){
        boolean[] isVisited = new boolean[linkedList.length];

        for(int i = 0; i < linkedList.length; i++){
            isVisited[i] = false;
        }

        Queue queue = new LinkedList<>();
        int currentNode = 1;
        int nextNode = 0;

        queue.add(currentNode);
        isVisited[currentNode] = true;

        while(!queue.isEmpty()){
            currentNode = (int)queue.remove();
            System.out.println("currentNode = " + currentNode);

            for(int i = 0; i < linkedList[currentNode].size(); i++){
                nextNode = (int)linkedList[currentNode].get(i);
                if(!isVisited[nextNode]){
                    queue.add(nextNode);
                    isVisited[nextNode] = true;
                }
            }
        }
    }
}

  BFS는 최단 경로 알고리즘의 원형으로 BFS만으로도 최단경로를 찾을 수 있다.