DFS와 BFS 자바로 구현하기

소스 코드

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);
        }
    }

    //DFS 함수
    void dfs() {
        dfs(0);
    }

    void dfs(int index) {
        Node root = nodes[index];
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        root.marked = true;

        //stack 이 빌 때까지 반복
        while (!stack.isEmpty()) {
            Node r = stack.pop();
            for (Node n : r.adjacent) {
                // 방문 하지 않은 노드만 스택에 추가하도록 조건 설정
                if (n.marked == false) {
                    n.marked = true;
                    stack.push(n);
                }
            }
            // 방문하고 나서 root 출력
            visit(r);
        }
    }

    // BFS 함수
    void bfs() {
        bfs(0);
    }

    void bfs(int index) {
        Node root = nodes[index];
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        root.marked = true;

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

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

    //재귀를 사용한 DFS
    void dfsR(Node r) {
        if (r == null) return;

        r.marked = true;
        visit(r); // 먼저 출력

        for (Node n : r.adjacent) {
            if (n.marked == false) {
                // 재귀 호출
                dfsR(n);
            }
        }
    }

    //시작 노드를 다양하게 테스트 하기 위한 함수
    void dfsR(int index) {
        Node r = nodes[index];
        dfsR(r);
    }

    void dfsR() {
        dfsR(0);
    }

    void visit(Node node) {
        System.out.print(node.data + " ");
    }
}

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("=== DFS 실행 ===");
        g.dfs();

        //System.out.println("=== BFS 실행 ===");
        //g.bfs();

        //System.out.println("=== DFS 재귀 실행 ===");
        //g.dfsR();
    }
}

간단하게 DFS와 BFS를 자바로 구현했다.

addEdge 메소드는 간선을 추가해서 두 노드를 연결하겠다는 의미이다.

0에 1을 연결하고,
1에 2,3을 연결, 2에 3,4를 연결... 이런 식으로 표현되었다.

또한 dfs,bfs,dfsR 메소드는 각각 Stack과 Queue 를 하나씩 제거하면서 돌고 있기 때문에 따로따로 실행해야 한다.