[자료구조와 알고리즘] 그래프(Graph) 개념

그래프 (Graph)

• 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多 의 관계를 지니는 원소들을 표현하기 위한 자료구조
• 그래프 G
  • 객체를 나타내는 정점 Vertex와 객체를 연결하는 간선 edge의 집합
  • G = (V, E)
    • V : 그래프에 있는 정점들의 집합
    • E : 정점을 연결하는 간선들의 집합
• 그래프의 예 : 버스나 지하철 노선도, 인스타그램의 following/follower 관계 지도

그래프의 종류

1. 무방향 그래프 (undirected graph)

• 두 정점을 연결하는 간선의 방향이 없는 그래프
• 정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현
  • (Vi, Vj)와 (Vj, Vi)는 같은 간선을 의미
  • 간선을 나타내는 정점의 쌍에는 순서가 존재하지 않는다.

• V(G) = {A, B, C, D} E(G) = {(A, B), (A, C), (A, D), (B, D), (C, D)}

2. 방향 그래프 (directed graph)

• 간선이 방향을 가지고 있는 그래프
  • Vi, Vj를 연결하는 간선 Vi->Vj를 <Vi, Vj>로 표현
  • Vi를 꼬리(tail), Vj를 머리(head)라고 한다.
  • <Vi, Vj>와 <Vj, Vi>는 서로 다른 간선을 의미

• V(G) = {A, B, C, D} E(G) = { <A, B>, <A, D>, <B, D>, <C, A>, <D, C> }

3. 완전 그래프 (Complete graph)

• 각 정점에서 다른 모든 정점을 연결하여 가능한 최대의 간선 수를 가진 그래프
  • 정점이 n개인 무방향 그래프의 최대 간선 수: n(n-1)/2개
  • 정점이 n개인 방향 그래프의 최대 간선 수: n(n-1)개

4. 부분 그래프 (Subgraph)

• 원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프
• 그래프 G와 그래프 G'와의 관계
  • V(G')⊆V(G), E(G')⊆E(G)

5. 가중 그래프 (Weight graph)

• 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프

그래프 관련 용어

• 경로(path) : 정점 Vi로부터 정점 Vj까지 갈 수 있는 길을 순서대로 나열한 것
• 경로의 길이(path length) : 경로 상에 있는 간선의 수
• 단순 경로(simple path) : 경로 상에서 처음과 마지막을 제외한 모든 정점들이 서로 다른 경로
• 사이클(cycle) : 처음과 마지막 정점이 같은 단순 경로 (순환이 가능한 단순 경로)
• DAG (directed acyclic graph) : 방향 그래프이면서 사이클이 없는 그래프
• 연결 그래프
  • 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프, 떨어져 있는 정점이 없는 그래프
  • 그래프에서 두 정점 Vi에서 Vj까지의 경로가 있으면 정점 Vi와 Vj가 연결되었다고 함
  • 트리는 사이클이 없는 연결 그래프이다.
• 간선 (Vi, Vj)
  • 두 정점 Vi와 Vj는 인접(adjacent)되어 있다.
  • 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속(incident)되어 있다.
• 차수(degree) : 정점에 부속되어 있는 간선의 수
  • 방향 그래프의 정점의 차수 = 진입차수 + 진출차수
    • 진입차수(in-degree) : 정점을 머리로 하는 간선의 수
    • 진출차수(out-degree) : 정점을 꼬리로 하는 간선의 수