그래프 이론

그래프란? 

연결 데이터를 저장 할 수 있는 자료구조를 의미한다.

자료구조에는 많은 형태가 있다. 예를 들어 스택, 큐, 링크드 리스트...등등

선형 구조, 비선형 구조, 계층 구조 등이 존재한다.

여기서 그래프는 선형적, 계층적 구조를 가진다.

그래프

그럼 왜  CS(Computer Science)에서 그래프를 다루어야 할까?

바로 그래프는 기존의 자료구조에서 표현 할 수 없는 데이터를 나타낼 수 있기 때문이다.

예를들어 SNS에서도 많이 사용된다. 누가 누구를 팔로우, 팔로잉 했는지 또 누구와 관련이 있는지 

알아 낼 수 있기 때문이다. 또한 탐색에서도 많이 이용된다. 깊이 우선 탐색, 넓이 우선 탐색 등 다양하게

응용 및 이용 될 수 있기 때문이다.

BFS, DFS

이러한 그래프는 여러 종류가 존재하는데, 무방향 그래프, 방향 그래프, 가중치 그래프로 나누어 볼 수 있다.

일단 그래프에 대한 기본적인 용어를 설명 하겠다.

방향 그래프, 무방향 그래프

그래프에서는 각 데이터를 노드 라고 부른다. 그리고 이러한 노드들을 연결하는것을 엣지라고 부른다.

그리고 이러한 엣지로 연결된 노드를 인접 한다라고 부른다.

그래프에서 각 노드에서 다른 노드로 가는 길을 경로 라고 한다.

노드와 엣지

그리고 이러한 경로를 통해 한 노드에서 다른 노드로 다시 돌아오는 경로를 싸이클 이라고 부른다.

예를 들어 위의 그래프에서는 A>C>D>A

각 노드들은 차수(degree)를 가지고 있다. 여기서 차수는 각 노드에 연결된 엣지를 의미한다.

그런데 여기서 차수는 방향 그래프에서는 입력 차수, 출력 차수로 나누어 볼 수 있다.

왜냐하면 방향 그래프에서는 방향때문에 경로가 정해져 있기 때문이다.

위의 방향 그래프에서 C를 보면 C에서 나가는 출력 차수는 1이지만 입력 차수는 0인것이 그 예이다.

가중치 그래프

가중치 그래프는 각 경로에 있는 엣지의 가중치를 이용하여 경로의 거리나 노드의 가중치를 알 수 있는 그래프이다.

이러한 가중치 그래프를 이용하면 좀 더 현실적으로 그래프를 적용할 수 있다.

예를 들어 지역을 생각해보자. 경기도에서 제주도까지의 거리를 100이라고 하자. 

그리고 부산에서 제주도까지의 거리를 40이라고 하자. 가중치 그래프라면 각 경로에 가중치를 표함으로써

어떤 노드에서 어떤 노드까지의 거리나 가중치를 비교 할 수 있어서 어떤 노드에서 어떤 노드까지의 경로가 더 짧은지

혹은 비용이 많이 나오는지 가늠하거나 알 수 있다. 만약 비가중치 그래프라면 어떤 경로를 이용하는것이 최단 경로인지

혹은 비용이 적게 드는지 알 수 없을 것이다. 현실에서도 이는 고스란히 적용된다. 

네비게이션을 생각해보면 알 수 있을것이다. 

 

오늘은 그래프의 용어와 개념에 대해 간단히 정리하였다. 

다음에는 이러한 용어와 개념을 바탕으로 코딩하여 그래프를 실질적으로 사용해보겠다.