[알고리즘] 그래프 알고리즘(DFS, BFS)

Junkyu_Kang·2024년 5월 31일

그래프 알고리즘 개요

그래프는 노드(정점)와 이들을 연결하는 간선들로 이뤄진 자료 구조이다. 다양한 문제를 이런 구조로 표현하고 해결할 수 있다. 여러 그래프 알고리즘은 각기 다른 방식으로 그래프를 탐색하고 최적의 경로를 찾거나 최소 비용을 계산하는 등의 작업을 수행한다.

BFS, DFS

출처 : https://velog.io/@vagabondms/DFS-vs-BFS

1. 깊이 우선 탐색 (DFS)

설명: DFS는 그래프의 깊은 부분을 우선적으로 탐색하고, 더 이상 갈 데가 없으면 되돌아가 다른 경로를 탐색한다.
자바 코드 예시:

import java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> adjList;

    public Graph(int vertices) {
        adjList = new HashMap<>();
        for (int i = 0; i < vertices; i++) {
            adjList.put(i, new LinkedList<>());
        }
    }

    void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
    }

    void DFS(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        for (int adj : adjList.get(vertex)) {
            if (!visited[adj]) {
                DFS(adj, visited);
            }
        }
    }

    public void DFS(int startVertex) {
        boolean[] visited = new boolean[adjList.size()];
        DFS(startVertex, visited);
    }

    public static void main(String[] args) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("DFS starting from vertex 2:");
        g.DFS(2);
    }
}

2. 너비 우선 탐색 (BFS)

설명: BFS는 시작 정점에서 가까운 노드부터 방문하고 점차 멀어지면서 탐색한다.
자바 코드 예시:

import java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> adjList;

    public Graph(int vertices) {
        adjList = new HashMap<>();
        for (int i = 0; i < vertices; i++) {
            adjList.put(i, new LinkedList<>());
        }
    }

    void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
    }

    void BFS(int startVertex) {
        boolean[] visited = new boolean[adjList.size()];
        Queue<Integer> queue = new LinkedList<>();

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

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

            for (int adj : adjList.get(vertex)) {
                if (!visited[adj]) {
                    visited[adj] = true;
                    queue.add(adj);
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("BFS starting from vertex 2:");
        g.BFS(2);
    }
}

장점 / 단점

BFS

장점:
너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장한다.(ex 미로찾기)
최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다.
노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리하다.

단점:
재귀호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색 할 노드들을 저장하기 때문에 노드의 수가 많을 수록 필요없는 노드들까지 저장해야 하기 때문에 더 큰 저장공간 필요하다.
노드의 수가 늘어나면 탐색해야하는 노드가 많아지기 때문에 비효율적일 수 있다.