그래프

Intro

그래프 개념을 이해하고 실제 코드로 구현해보자!!

1️⃣ 그래프 개념

• 정점과 간선으로 구성된 자료구조
• 지도,네트워크 같은 복잡한 관계 표현에 용이하다.

용어

용어	설명
정점(Vertex, Node)	그래프에서 데이터 하나를 의미하는 점
간선(Edge)	정점과 정점을 연결하는 선, 관계를 나타냄
방향 그래프(Directed Graph)	간선에 방향이 있는 그래프
무방향 그래프(Undirected Graph)	간선에 방향이 없는 그래프
가중치(Weight)	간선에 부여된 비용이나 값
인접(Adjacent)	두 정점이 간선으로 직접 연결되어 있는 상태
차수(Degree)	정점에 연결된 간선의 개수 (방향 그래프는 진입차수/진출차수)

종류

• 방향/무항향 그래프
• 가중치/비가중치 그래프
• 연결/비연결 그래프 (모든 정점의 연결 여부)
• 순환/비순환 그래프 (사이클 유무)

구현 방법

1. 인접 행렬

• 2차원 배열(행렬)로 표현
• matrix[i][j]에 간선 존재 여부 또는 가중치 저장
• 정점이 n개면 n x n 크기의 배열 생성

2. 인접 리스트

• 각 정점마다 연결된 정점들의 목록을 저장
• 리스트 배열 또는 리스트를 원소로 하는 리스트 구조 사용

구분	인접 행렬 (Adjacency Matrix)	인접 리스트 (Adjacency List)
장점	- 간선 존재 여부를 O(1) 시간에 즉시 확인 가능	- 간선 탐색 시 해당 정점에 연결된 정점만 순회하여 빠름
	- 구현이 간단	- 메모리 사용이 효율적 (O(n + m))
단점	- 희소 그래프에서 메모리 비효율적 (O(n²))	- 간선 존재 여부 확인 시 인접 리스트를 모두 확인해야 해서 느림
	- 노드 번호가 크면 배열 크기가 커져 비효율적	- 인접 행렬보다 구현이 다소 복잡

2️⃣ 그래프 탐색

그래프를 탐색하는 방법에는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있다.

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

| 한 정점에서 출발해 가능한 깊게 내려가며 방문하는 탐색

특징

• 스택 자료구조 사용
• 경로 탐색, 사이클 검출 등에 활용

동작 방식

1. 시작 정점 방문 및 방문 기록 표시
   ㄴ 시작 정점을 방문 처리하고, 방문 여부를 기록한다.

2. 시작 정점을 스택에 push
   ㄴ 탐색할 정점들을 관리하기 위해 스택에 시작 정점을 넣는다.

3. 스택이 빌 때까지 다음 동작 반복
   ㄴ 1) 스택에서 정점 하나를 pop 한다.
   ㄴ 2) 그 정점이 아직 방문하지 않은 상태라면 방문 처리하고 출력한다.
   ㄴ 3) 그 정점과 연결된 인접 정점들 중 방문하지 않은 정점들을 모두 스택에 push 한다.

4. 모든 연결된 정점이 방문되면 탐색 종료

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

| 한 정점에서 출발해 인접한 정점부터 차례로 방문하는 탐색

특징

• 큐 자료구조 사용
• 최단 경로 탐색에 유리

동작방식

1. 시작 정점 방문 및 방문 기록 표시
   ㄴ 시작 정점을 방문 처리하고, 방문 여부를 기록한다.

2. 시작 정점을 큐에 enqueue
   ㄴ 탐색할 정점들을 관리하기 위해 큐에 시작 정점을 넣는다.

3. 큐가 빌 때까지 다음 동작 반복
   ㄴ 1) 큐에서 정점 하나를 dequeue 한다.
   ㄴ 2) 그 정점을 처리(출력 등)한다.
   ㄴ 3) 그 정점과 연결된 인접 정점들 중 방문하지 않은 정점들을 모두 방문 처리하고 큐에 enqueue 한다.

4. 모든 연결된 정점이 방문되면 탐색 종료

3️⃣ 구현

인접행렬

import java.util.*;

public class GraphSearchMatrix {
    static int n = 5;  // 정점 개수
    static int[][] adjMatrix = new int[n][n];  // 인접 행렬
    static boolean[] visited;

    // DFS (재귀)
    public static void dfs(int node) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int i = 0; i < n; i++) {
            // 간선이 존재하고 방문하지 않은 정점이면 재귀 호출
            if (adjMatrix[node][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }

    // BFS (큐)
    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited = new boolean[n];
        visited[start] = true;
        queue.offer(start);

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

            for (int i = 0; i < n; i++) {
                // 간선이 존재하고 방문하지 않은 정점이면 큐에 추가
                if (adjMatrix[node][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    queue.offer(i);
                }
            }
        }
    }

    public static void main(String[] args) {
        // 인접 행렬 초기화 
        adjMatrix[0][1] = 1; adjMatrix[1][0] = 1;
        adjMatrix[0][2] = 1; adjMatrix[2][0] = 1;
        adjMatrix[1][3] = 1; adjMatrix[3][1] = 1;
        adjMatrix[1][4] = 1; adjMatrix[4][1] = 1;

        visited = new boolean[n];

        System.out.print("DFS: ");
        dfs(0);  // 0번 정점부터 DFS
        System.out.println();

        System.out.print("BFS: ");
        bfs(0);  // 0번 정점부터 BFS
    }
}

인접리스트

import java.util.*;

public class GraphSearchList {
    static int n = 5;  // 정점 개수
    static List<List<Integer>> adjList = new ArrayList<>();
    static boolean[] visited;

    // DFS (재귀)
    public static void dfs(int node) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int next : adjList.get(node)) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }

    // BFS (큐)
    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited = new boolean[n];
        visited[start] = true;
        queue.offer(start);

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

            for (int next : adjList.get(node)) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
    }

    public static void main(String[] args) {
        // 인접 리스트 초기화
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }

        // 간선 추가 
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(1, 3);
        addEdge(1, 4);

        visited = new boolean[n];

        System.out.print("DFS: ");
        dfs(0);  // 0번 정점부터 DFS
        System.out.println();

        System.out.print("BFS: ");
        bfs(0);  // 0번 정점부터 BFS
    }

    // 무방향 간선 추가 메서드
    public static void addEdge(int u, int v) {
        adjList.get(u).add(v);
        adjList.get(v).add(u);
    }
}

DFS (stack)

void dfs(int start) {
    Stack<Integer> stack = new Stack<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (!visited[node]) {
            visited[node] = true;
            for (int next : adj[node]) {
                if (!visited[next]) stack.push(next);
            }
        }
    }
}

BFS (PriorityQueue)