그래프 개념

그래프 (Graph)

그래프란?

그래프는 객체(노드 또는 정점) 간의 연결 관계(간선)를 표현하는 자료구조

그래프는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 표현된다.

• 정점: A, B, C, D, E, F
• 간선: A-B, B-C, B-E, C-D, E-D, E-F

그래프의 활용 예시

분야	정점 (Vertex)	간선 (Edge)
교통/지도	도시, 정류장	도로, 철도 등 이동 경로
네트워크	컴퓨터, 라우터	통신 회선
소셜 미디어	사용자	친구/팔로우 관계

 

그래프의 분류

1. 방향 여부

• 무방향 그래프 (Undirected)
  간선에 방향이 없음. A↔B 양방향 연결
• 방향 그래프 (Directed)
  간선에 방향 있음. A→B는 가능하지만 B→A는 불가
  • indegree: 들어오는 간선 수
  • outdegree: 나가는 간선 수

2. 간선 중복 여부

• 단순 그래프 (Simple Graph)
  • 자기 자신을 연결하는 간선 없음 (Self-loop 없음)
  • 정점 간 간선이 최대 하나
• 다중 그래프 (Multigraph)
  • 정점 간 여러 간선 가능
  • Self-loop 허용

* 일반적인 알고리즘 문제에서는 단순 그래프를 다루는 경우가 많다.

3. 가중치 존재 여부

• 비가중치 그래프 (Unweighted)
  • 모든 간선의 비용이 동일하거나 없음
• 가중치 그래프 (Weighted)
  • 각 간선마다 거리, 비용 등의 값이 존재
  • 예: Dijkstra, Floyd-Warshall 알고리즘에 사용

4. 사이클 존재 여부

• 순환 그래프 (Cyclic)
  • 사이클이 존재하는 그래프
• 비순환 그래프 (Acyclic)
  • 사이클이 존재하지 않음
  • DAG (Directed Acyclic Graph)는 위상 정렬 등에서 활용

그래프 표현 방식

1. 인접 행렬 (Adjacency Matrix)

• 2차원 배열로 연결 정보를 저장
• 1은 연결, 0은 비연결
• 공간 복잡도: O(V^2)
• 모든 정점 간 연결 상태를 빠르게 확인할 수 있음

int[][] matrix = {
    {0, 1, 0, 0, 0, 0}, // A
    {1, 0, 1, 0, 1, 0}, // B
    {0, 1, 0, 1, 0, 0}, // C
    {0, 0, 1, 0, 1, 1}, // D
    {0, 1, 0, 1, 0, 1}, // E
    {0, 0, 0, 1, 1, 0}  // F
};

• 특징:
  • 대칭 구조 → 무방향 그래프
  • Self-loop가 없으면 대각선은 0
  • 정점 수가 많고 간선이 적은 경우 공간 낭비 발생

2. 인접 리스트 (Adjacency List)

• 각 정점에 연결된 노드 목록을 리스트로 저장
• 메모리 효율적 → 희소 그래프에 적합
• 공간 복잡도: O(V + E)

리스트 기반 구현

List<List<Integer>> graph = List.of(
    List.of(1),
    List.of(0, 2, 4),
    List.of(1, 3),
    List.of(2, 4, 5),
    List.of(1, 3, 5),
    List.of(3, 4)
);

딕셔너리 기반 구현

Map<String, List<String>> graph = new HashMap<>() {{
    put("A", List.of("B"));
    put("B", List.of("A", "C", "E"));
    put("C", List.of("B", "D"));
    put("D", List.of("C", "E", "F"));
    put("E", List.of("B", "D", "F"));
    put("F", List.of("D", "E"));
}};

• 특징:
  • 연결된 노드만 저장 → 메모리 절약
  • 코딩 테스트에서 가장 많이 사용

3. 암시적 그래프 (Implicit Graph)

• 명시적으로 그래프를 저장하지 않고, 이동 규칙이나 수식을 기반으로 탐색
• 예: 미로 탐색, 체스판 이동, 상태 전이 문제 등

// 예: 2차원 좌표 이동
int[][] directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};