[자료 구조] 그래프 자료구조 :: Graph Data Structure

그래프(Graph)란?

출처 : stackoverflow

그래프란? 쉽게 한 문장으로 설명한다면, 현실 세계의 관계를 시각적으로 나타낼 수 있는 구조. 라고 할 수 있다.

우리는 일상에서 다음과 같은 곳에서 그래프를 사용한다.

• 네비게이션 최단 경로
• 네트워크 통신
• 친구 관계

그래프를 사용하면 객체간의 관계를 쉽게 나타낼 수 있다는 장점으로 많이 사용한다.

 

이를 전문적인 용어로 말 한다면 정점과 간선의 집합으로 구성되며 수학적으로는 G = (V, E)의 관계로 나타난다. 처음 보는 사람들은 이해가 안 갈 수도 있는데, 한 번 따라가 보자.

그래프의 종류

그래프의 종류는 다음과 같은 세 가지로 나뉜다.

출처 : https://www.ritambhara.in/adjacency-matrix-implementation-of-graph-data-structure/

무방향 그래프 (Undirected Graph)

무항향 그래프는 간선에 방향이 표시되어있지 않은 그래프를 무방향 그래프라고 한다.

여기서 하나의 간선은 양방향으로 갈수 있는 길을 의미하고 (A, B)나 (B, A)은 같은 간선이 된다.

방향 그래프 (Directed Graph)

간선에 방향이 존재하는 그래프를 방향 그래프라고 한다.

보통 화살표로 표시되는데 차도의 일방통행이라고 생각하면 쉽다.

 

<A, B>를 방향이 있는 그래프에서 표시하는데 <A, B>는 정점 A에서 B로만 갈 수 있는 간선을 나타낸다. 그 말은 당연히 <A, B>와 <B, A>는 다른 그래프를 뜻한다.

가중치 그래프 (Weighted Graph)

간선의 비용이나 가중치가 할당된 그래프를 가중치 그래프라고 한다.

그래프의 용어

• 인접 정점

  간선에 의해 직접 연결된 그래프

• 정점의 차수

  정점에 연결된 간선의 수

• 경로

  간선을 따라 갈 수 있는 길

• 경로의 길이

  경로를 구성하는되 사용된 간선의 수

• 단순 경로와 사이클

  경로 중에서 반복되는 간선이 없는 경로

• 연결 그래프

  모든 정점들 사이에 경로가 존재하면 연결 그래프

• 트리

  사이클을 가지지 않는 연결 그래프

• 완전 그래프

  모든 정점 간에 간선이 존재하는 그래프