[알고리즘/C++] 그래프 이론 (Graph)

그래프 (Graph)

정점(vertex)과 이를 잇는 간선(edge)으로 이루어진 수학적 구조이다. 현실 세계의 문제를 모델링하고 알고리즘을 적용하는데 사용된다. 다양한 현상이나 데이터 간의 관계를 시각적으로 표현할 수 있다.

정점, 간선 두 개의 유한집합으로 표기할 수 있다.

$V = \{v_1, v_2, v_3,…,v_n\}$

$E = \{e_1, e_2, e_3,…,e_m\}$

정점(vertex)

점 혹은 원으로 표현된다. 노드 (node)라고 부르기도 한다.

간선 (edge)

두 개의 정점을 연결하는 선이다. 간선의 특성에 따라 그래프의 종류가 달라진다.

차수 (degree)

정점에서 나가는 간선의 개수이다.

Directed Graph vs Undirected Graph

출처 : https://www.geeksforgeeks.org/what-is-the-difference-between-an-undirected-and-a-directed-graph/

정점 A, B를 연결하는 간선을 가정하자. 이때 A → B, B → A 양방향에 대해 간선이 정의되어있으면 방향성을 가지지 않는 Undirected Graph이다.

만약 A → B, 한 방향에 대해서만 간선이 유효할 때, 이때는 간선이 방향성을 가진 Directed Graph이다.

Weighted Graph vs Unweighted Graph

간선이 두 정점 사이가 연결되어 있는지 여부에 대한 정보만 가지고 있을 때 해당 그래프를 가중치가 없는 Unweighted Graph라고 부른다.

간선이 두 정점간의 거리와 같은 정보를 담고 있을 때, 해당 그래프를 가중치를 가진 Weighted Graph라고 한다.

Complete Graph

모든 정점이 서로 간선으로 연결되어있는 경우 완전 그래프(Complete Graph)라고 한다.

Regular Graph

모든 정점의 차수(degree)가 k로 같은 경우 K-Regular Graph라고 한다.

출처 : https://www.geeksforgeeks.org/introduction-to-graphs-data-structure-and-algorithm-tutorials/?ref=outind

Cycle Graph

Regular Graph 중 2-Regular Graph는 각 노드의 간선이 2개씩 있는 그래프 이다. 해당 그래프는 하나의 사이클을 만드므로 Cycle Grpah라고 부른다.

Cyclic Graph

그래프에서 적어도 하나의 사이클을 가지고 있는 그래프를 Cyclic Graph라고 한다.

출처 : https://www.geeksforgeeks.org/introduction-to-graphs-data-structure-and-algorithm-tutorials/?ref=outind

트리 (Tree)

트리는 그래프 한 종류로써, 그래프에서 사이클이 존재하지 않으며, 방향성이 없는 Unweighted Graph이다.

해당 형태의 그래프는 계층구조를 표현하는데 특화되어 있다.