BFS 를 사용해서 Graph에서 두 지점의 경로 찾기

소스 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Graph {
    static class Node {
        int data; // 값
        LinkedList<Node> adjacent; //인접한 노드, 자식 노드
        boolean marked; // 방문 유무

        Node(int data) {
            this.data = data;
            this.marked = false;
            adjacent = new LinkedList<>();
        }
    }
    Node[] nodes;

    Graph(int size) {
        nodes = new Node[size];
        for (int i = 0; i < size; i++) {
            nodes[i] = new Node(i);
        }
    }

    //자식 노드 추가하기, 양방향으로 추가함.
    void addEdge(int root, int child) {
        Node n1 = nodes[root];
        Node n2 = nodes[child];

        if (!n1.adjacent.contains(n2)) {
            n1.adjacent.add(n2);
        }

        if (!n2.adjacent.contains(n1)) {
            n2.adjacent.add(n1);
        }
    }

    void initMarks() {
        for (Node n : nodes) {
            n.marked = false;
        }
    }

    boolean search(int i1, int i2) {
        return search(nodes[i1], nodes[i2]);
    }

    //BFS로 구현
    boolean search(Node start, Node end) {
        initMarks();

        Queue<Node> queue = new LinkedList<>();
        queue.add(start);

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

            if (root == end) {
                return true;
            }

            for (Node n : root.adjacent) {
                if (n.marked == false) {
                    n.marked = true;
                    queue.add(n);
                }
            }
        }

        return false;
    }
}
/* 이렇게 생긴 그래프를 가지고 코드를 실행할 것
   0
  /
 1 -- 3     7
 |  / | \ /
 | /  |  5
 2 -- 4   \
            6 - 8
 */
public class DfsBfs {
    public static void main(String[] args) {
        Graph g = new Graph(9);

        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.addEdge(3, 5);
        g.addEdge(5, 6);
        g.addEdge(5, 7);
        g.addEdge(6, 8);

        System.out.println(g.search(1, 8));
    }
}

BFS 를 사용해서 그래프의 두 정점이 연결되는지 알아보는 코드를 작성했다. addEdge 메소드를 적절하게 주석 처리하면 그래프의 연결이 끊겨서 false 가 반환되는 것을 확인 할 수 있다.

시작(start) 노드를 가지고 와서 해당 노드에서 연결되는(adjacent) 노드들을 들리면서 Queue 에 넣는 작업을 반복한다. 그렇게 반복해서 연결된 root 노드가 내가 찾고자 하는 end 노드와 같다면 true를 return 하면서 마무리한다. 모든 노드를 돌았지만 답을 찾지 못한 경우 false 를 반환한다.

---

참고 영상

• [자료구조 알고리즘] Graph에서 두지점의 경로찾기

이렇게 두 번의 예제를 통해서 대충 BFS와 DFS를 알게 되긴 했다. 여기서는 계속 Graph와 Node 를 직접 구현해서 문제를 풀고 있는데 자바에서 제공하는 다른 방식이 있는지 알아봐야겠다. Stack 은 그대로 Stack 을 사용하면 되고 Queue 는 LinkedList, minHeap 은 PriorityQueue 가 있는 것처럼 Graph도 간단한 방법이 있을까? 더 찾아보고 공부해야겠다.