Imaginations crafted into real code.

그래프


📊 자바 그래프 구현 및 탐색 (간략 정리)

이번엔 자바에서 그래프를 구현하고 탐색하는 주요 방법을 핵심만 간략하게 정리하였다.

그래프 구현 방법

🔹 인접 행렬 (Adjacency Matrix)

  • 방법: 2차원 배열 graph[V][V]를 사용해 정점 간 연결 여부를 표시한다.
  • 장점: 두 정점 간 **연결 여부 확인이 O(1)**로 매우 빠르다.
  • 단점: 정점 V가 많으면 **메모리 사용량이 O(V²)**으로 많아 희소 그래프에 비효율적이다.

🔹 인접 리스트 (Adjacency List)

  • 방법: 각 정점에 연결된 정점들을 리스트(예: ArrayList<ArrayList<Integer>>)로 저장한다.
  • 장점: **메모리 사용량이 O(V + E)**로 효율적이라 희소 그래프에 좋다.
  • 단점: 특정 간선 존재 여부 확인 시 해당 리스트를 순회해야 해서 O(V) 시간이 걸릴 수 있다.

그래프 탐색

그래프의 모든 정점 또는 특정 정점을 방문하는 두 가지 주요 방법이다.

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

  • 방식: 한 방향으로 최대한 깊이 탐색한 후, 더 이상 갈 곳이 없으면 되돌아와 다른 경로를 탐색한다.
  • 구현: 주로 재귀를 이용해 구현한다.
  • 핵심: visited[] 배열로 방문 여부를 체크해서 무한 루프를 방지한다.
void dfs(int v) {
    visited[v] = true; 
    for (int i : graph[v]) { // 인접 리스트의 경우
        if (!visited[i]) { 
            dfs(i);
        }
    }
}

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

  • 방식: 시작 정점에서 가까운 정점부터 차례대로 너비 우선으로 탐색한다. 최단 경로 찾기에 유용하다 (가중치 없는 그래프에서).
  • 구현: 큐(Queue) 자료구조를 이용해 구현한다.
  • 핵심: visited[] 배열과 큐를 사용해서 단계별로 탐색한다.
void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.add(start);

    while (!queue.isEmpty()) {
        int v = queue.poll(); 
        for (int i : graph[v]) { // 인접 리스트의 경우
            if (!visited[i]) {
                visited[i] = true;
                queue.add(i);
            }
        }
    }
}