[자료구조 - 그래프] 그래프(Graph)의 정의와 종류

이전 포스터에서 자료구조를 선형, 비선형 구조로 구분하여 각 자료구조 별 특징을 나눠봤다. <- 이동하기

그 중 그래프틑 트리와 함께 비 선형구조로 해당된다.

이번 포스팅에서는 요즈음 코딩 테스트에서 1문제씩 꼭 나타나는 그래프에 대해 자세한 설명을 하도록 하겠다.

---

[Graph]

그래프란? 여러 대상들과 대상들 간의 1:1 관계를 도형으로 나타낸 것.

• 대상들은 하나의 정점(Vertex)로 표현된다. 각 정점은 기본적으로 Index를 부여하여 구분한다.
• 두 정점 사이의 관계는 간선(Edge)으로 표현한다. 간선은 단방향 혹은 양방향으로 표현 할 수 있으며, 가중치 등의 고유한 특정 값을 가질 수 있다.
• 그래프 G는 정점 집합 V = {정점들의 집합}과 간선 집합 E = {간선들의 집합}으로 구성되며 G(V, E) 라고 정의한다.

 

그래프 G (V, E)에 대해

• 인접(Adjacent) : 두 노드를 연결해주는 간선이 집합 G(V, E)에서 E에 존재하면, 두 노드는 인접한다고 정의한다.
• 인접 정점(Adjacent Vertex) : 간선에 의해 직접 연결된 정점이다.
• 경로(Path) : 두 노드를 이어주는 간선의 집합을 의미한다.
  • 같은 노드를 두 번 이상 거치지 않는 경로를 단순 경로라고 한다. 
  • 우리가 보통 알고있는 한붓 그리기는 '같은 노드를 두 번 이상 거치지 않고 모서리를 한 번만 지나면서 모두 지나는 경로가 존재하는 그래프'를 오일러의 법칙이라 한다.
• 연결(Connected) : 경로가 존재하는 두 노드는 연결되어 있다고 정의하며, 임의의 서로 다른 두 노드 U, V에 대해 항상 경로가 존재하는 그래프를 Connected Graph(연결 그래프)라고 한다.

---

그래프의 종류

1. 연결 그래프(Connected Graph) : 모든 두 노드 쌍 사이에 항상 경로가 존재하는 그래프이다

연결 그래프

 

2. 완전 그래프(Complete Graph) : 모든 두 노드 쌍 사이에 항상 간선이 존재하는 그래프이며, 간선이 O(N^2)개 존재한다. 완전 그래프는 연결 그래프의 한 종류이다.
(무방향 완전 그래프의 정점 수(n)일 때 간선의 수를 구하는 공식 = n * (n - 1) / 2)

완전 그래프

3. 비연결 그래프 : 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 그래프이다. 

비연결 그래프

4. 무방향 그래프 : 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
정점 A와 정점 B를 연결하는 간선은 (A, B) 혹은 (B, A)와 같이 정점의 쌍으로 표현한다.

무방향 그래프

5. 방향 그래프 : 간선에 방향성이 존재하는 그래프이다.
A->B로만 갈 수 있는 간선은 <A, B>로 표시한다. 무방향 그래프와 다르게 <B, A>로 나타낼 수 없다. 즉, <A, B> <B, A>는 다른 의미다.

방향 그래프

6. 가중치 그래프 : 간선에 비용이나 가중치가 할당된 그래프이다.

가중치 그래프

7. 순환 그래프 : 단순 경로의 시작 정점과 종료 정점이 동일한 그래프이다.

순환 그래프

8. 비순환 그래프 : 사이클이 없는 그래프이다. 

---

[Tree]

트리란? 사이클이 존재하지 않은 연결 그래프다.

• 정점의 수 N에 대해 간선의 수는 항상 N-1이다.
• 두 노드 사이의 경로는 하나밖에 존재하지 않는다.