[자료구조] 그래표(Graph)란?

개요

---

그래프는 어떤 데이터 사이의 인접한 정보를 저장하는 자료구조이다.

트리(Tree)도 그래프의 한 종류이다.

Objects와 Relationship으로 이루어져 있는데 Object는 저장하고자 하는 객체를 의미하며 Relationship은 객체와의 관계성을 의미한다.

---

Undirected Graphs

---

undirected graph는 방향이 없는 그래프를 의미한다.

표현 식은 다음과 같다.

 

E = {{v₁, v₂},{v₃, v₅},{v₄, v₈},{v₄, v₉},{v₆, v₉}} 

undirected graphs

그래프를 {v₁, v₂}라고 정의할 시, {v₂, v₁} 이렇게 역으로도 모두 있다고 가정한다.

해당 그래프에서 E의 절대값은 5이며 각 노드들의 경로와 차수도 구할 수 있다.

v₇과 같은 노드의 경로는 trivial path라고 하며 길이는 0이다.

 

그래프의 상태는 연결되어 있는지, 안되어 있는지로 나뉜다.

연결되어 있을 경우 connected, 연결되어 있지 않을 경우 unconnected이다.

위의 그래프를 예시로 들면 {v₁, v₂} 그래프와 {v₅, v₃} 그래프는 서로 연결되어 있지 않으므로 unconnected 상태이다. 

 

undirected graph에서 모든 선분(edge)을 구하는 공식은 다음과 같다.

식이 꽤나 복잡한데 알고 나면 별것도 아닌 식이다.

식에서 V는 노드의 개수를 의미한다.

V개의 노드가 있는 undirected graph에서 V를 2로 나눈 값에서 V2를 빼면 최대 선분의 개수를 구할 수 있다.

---

Weighted Graphs

---

weighted graph는 연결된 노드 사이에 숫자나 값을 부여한 그래프이다.

비용 등을 표현할 때 사용한다.

weighted graphs

길이는 노드에서 노드까지 가는 값들의 합이다.

예를 들어 A D G 의 값은 5.1 + 3.7 = 8.8 이다.

이 그래프를 활요하여 임계 경로(shortest past)등을 찾을 수 있다.

---

Directed Graph

---

directed graph는 undirected graph와 다르게 방향성을 가진다.

식은 다음과 같다.

E = {(v₁, v₂),(v₃, v₅),(v₅, v₃),(v₆, v₉),(v₈, v₄),(v₉, v₄)}

directed graph

in_degree는 노드로 들어오는 edge 개수이고 out_degree는 노드에서 출발하는 edge 개수이다.

예를 들어 v₁의 in_degreed와 out_degree는 다음과 같이 표현할 수 있다.

 

in_degree(v₁) = 0   out_degree(v₁) = 2

 

in_degree와 out_degree를 알면 source와 sink도 알 수 있다.

source는 in_degree가 0인 노드를 말하고 sink는 out_degree가 0인 노드를 의미한다.

해당 그래프에서 source는 v1, v6, v7, v8이 있고 sink는 v2, v4, v7이 있다.

 

pair 노드간의 경로에 있어 방향성을 고려했을 때, pair간에 경로가 존재한다면 strongly connected라고 한다.

방향성을 무시하고 연결성을 따졌을 때, 그래프가 연결되어 있다면 weakly connected라고 한다.

 

directed graph도 경로마다 값을 부여할 수 있으며, directed graph의 경로에 값이 부여된 그래프를 Weighted Directed Graph라고 한다.