자료구조 · 알고리즘 기초집LESSON 19

그래프 기초: 정점·간선·인접 리스트 표현

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

19강. 그래프 기초: 정점·간선·인접 리스트 표현

1. 이번 강의에서 해결할 문제

여러 갈래와 순환이 있는 스테이지 연결은 부모 하나를 가정하는 트리로 표현할 수 없습니다.

2. 학습 목표

3. 핵심 개념

그래프는 정점 집합과 정점을 잇는 간선 집합입니다. 이동이 양방향이면 무방향, 한쪽만 가능하면 방향 그래프입니다. 인접 리스트는 각 정점의 이웃만 저장해 V개 정점과 E개 간선에 O(V+E) 공간을 사용합니다. 인접 행렬은 간선 존재 확인이 O(1)이지만 O(V²) 공간이 필요해 희소 그래프에는 낭비가 큽니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/StageGraph.java

src/StageGraph.java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class StageGraph {
    private final Map<Integer, List<Integer>> adjacent = new HashMap<>();

    void addStage(int stage) { adjacent.computeIfAbsent(stage, key -> new ArrayList<>()); }
    void connect(int a, int b) {
        addStage(a); addStage(b);
        adjacent.get(a).add(b);
        adjacent.get(b).add(a);
    }
    List<Integer> neighbors(int stage) {
        return List.copyOf(adjacent.getOrDefault(stage, List.of()));
    }

    public static void main(String[] args) {
        StageGraph graph = new StageGraph();
        graph.connect(1, 2); graph.connect(1, 3); graph.connect(3, 4);
        System.out.println("1의 이웃: " + graph.neighbors(1));
        System.out.println("4의 이웃: " + graph.neighbors(4));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/StageGraph.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/StageGraph.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\StageGraph.java
java -cp .\out StageGraph

예상 결과: 1의 이웃 [2, 3]과 4의 이웃 [3]이 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

무방향 간선 a-b는 a 목록에 b, b 목록에 a를 모두 추가합니다. 정점 추가는 평균 O(1), 이웃 조회는 Map 접근 평균 O(1) 뒤 차수 d만큼 복사해 O(d)입니다. 전체 저장 공간은 무방향 간선을 두 번 저장해도 점근적으로 O(V+E)입니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ