BFS and DFS with Java

BFS(Breadth-First Search, 너비 우선 탐색)와 DFS(Depth-First Search, 깊이 우선 탐색)는 그래프를 탐색하는 두 가지 기본적인 방법입니다.

너비 우선 탐색 (BFS)
BFS는 그래프의 가장 가까운 노드부터 탐색하는 방식입니다. 즉, 시작 노드로부터 거리에 따라 순차적으로 탐색합니다. BFS는 큐(Queue)를 사용하여 구현합니다.

특징: 모든 노드를 방문할 때까지 각 노드를 거리 순으로 방문합니다.
사용 경우: 최단 경로를 찾거나, 그래프의 모든 노드를 방문하는 경우에 유용합니다.
깊이 우선 탐색 (DFS)
DFS는 그래프의 노드를 깊이 우선으로 탐색하는 방식입니다. DFS는 스택(Stack) 또는 재귀 함수를 사용하여 구현합니다.

특징: 하나의 경로를 끝까지 탐색한 후 다른 경로를 탐색합니다.
사용 경우: 모든 가능한 경로를 탐색하거나, 해결책이 깊이 숨어 있을 때 유용합니다.

import java.util.*;

public class BFSExample {
    private LinkedList<Integer> adjLists[];
    private boolean visited[];

    // 그래프 초기화
    BFSExample(int vertices) {
        adjLists = new LinkedList[vertices];
        visited = new boolean[vertices];

        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList<Integer>();
    }

    // 간선 추가
    void addEdge(int src, int dest) {
        adjLists[src].add(dest);
    }

    // BFS 구현
    void BFS(int vertex) {
        Queue<Integer> queue = new LinkedList<>();

        visited[vertex] = true;
        queue.add(vertex);

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

            Iterator<Integer> it = adjLists[v].listIterator();
            while (it.hasNext()) {
                int n = it.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    public static void main(String args[]) {
        BFSExample graph = new BFSExample(4);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        System.out.println("Following is Breadth First Traversal (starting from vertex 2)");
        graph.BFS(2);
    }
}

import java.util.*;

public class DFSExample {
    private LinkedList<Integer> adjLists[];
    private boolean visited[];

    // 그래프 초기화
    DFSExample(int vertices) {
        adjLists = new LinkedList[vertices];
        visited = new boolean[vertices];

        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList<Integer>();
    }

    // 간선 추가
    void addEdge(int src, int dest) {
        adjLists[src].add(dest);
    }

    // DFS 구현
    void DFS(int vertex) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        Iterator<Integer> it = adjLists[vertex].listIterator();
        while (it.hasNext()) {
            int n = it.next();
            if (!visited[n])
                DFS(n);
        }
    }

    public static void main(String args[]) {
        DFSExample graph = new DFSExample(4);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        System.out.println("Following is Depth First Traversal (starting from vertex 2)");
        graph.DFS(2);
    }
}