그래프 기본

1. 그래프의 기본 구성 요소

  1. 정점(Vertex, Node): 데이터 또는 객체를 나타냅니다.
  2. 간선(Edge): 정점 간의 관계 또는 연결을 나타냅니다.
  3. 가중치(Weight, 선택적 요소): 간선이 가질 수 있는 비용 또는 거리 값입니다.
  4. 방향성(Direction, 선택적 요소): 간선이 한쪽 방향으로만 연결될 수도 있고, 양방향으로 연결될 수도 있습니다.

2. 그래프의 종류

  1. 방향 그래프(Directed Graph, Digraph)
    • 간선이 방향을 가지며, 한 방향으로만 이동할 수 있음.
    • 예: 웹페이지 링크, 도로망(일방통행 도로)
  2. 무방향 그래프(Undirected Graph)
    • 간선이 방향이 없으며, 양방향으로 이동 가능.
    • 예: 친구 관계(서로 연결됨), 양방향 도로
  3. 가중치 그래프(Weighted Graph)
    • 간선에 가중치(비용, 거리, 시간 등)가 부여됨.
    • 예: 지도 내 최단 경로 탐색, 네트워크 트래픽 관리
  4. 비가중치 그래프(Unweighted Graph)
    • 간선에 가중치가 없음. 단순히 연결 유무만 나타냄.
  5. 연결 그래프(Connected Graph)
    • 모든 정점이 적어도 하나의 간선으로 연결됨.
  6. 비연결 그래프(Disconnected Graph)
    • 일부 정점이 다른 정점과 연결되지 않음.
  7. 트리(Tree)
    • 특별한 형태의 그래프로, 사이클이 없는 연결 그래프.

이웃(Neighbor)

정점 A의 이웃(Neighbor)은 정점 A와 간선으로 직접 연결된 정점들을 의미합니다.

  • 무방향 그래프(Undirected Graph)에서 정점 𝑣의 이웃:
    • 정점 𝑣와 간선으로 연결된 모든 정점들의 집합을 뜻합니다.
    • 예를 들어, 정점 𝐴가 정점 𝐵,𝐶,𝐷와 연결되어 있다면 𝐴의 이웃은 {𝐵,𝐶,𝐷} 입니다.
  • 방향 그래프(Directed Graph)에서 이웃의 개념:
    • 들어오는 이웃(In-neighbor): 정점 𝑣로 향하는 간선을 가진 정점들의 집합
    • 나가는 이웃(Out-neighbor): 정점 𝑣에서 나가는 간선을 가진 정점들의 집합
    • 예를 들어, 𝐴→𝐵이면, 𝐴는 𝐵의 In-neighbor, 𝐵는 𝐴의 Out-neighbor가 됩니다.

## 3. 그래프의 표현 방법

  1. 인접 행렬(Adjacency Matrix)
    • 그래프를 2차원 배열로 표현
    • 공간 복잡도: 𝑂(𝑉^2) (V는 정점의 개수)
    • 빠른 접근 속도를 가짐 (𝑂(1)), 하지만 메모리 사용량이 많음
    • 주로 정점 개수가 적고 간선이 많은 밀집 그래프(Dense Graph)에 적합
  2. 인접 리스트(Adjacency List)
    • 각 정점이 연결된 정점들을 리스트로 저장
    • 공간 복잡도: 𝑂(𝑉+𝐸) (E는 간선의 개수)
    • 메모리 사용이 효율적이며, 간선이 적은 희소 그래프(Sparse Graph)에 적합