C Data Structure - 그래프란?

드디어 그래프에 대한 포스팅이다. 여러가지 병행하며 정리할 것도 너무 많아서 ㅋㅋ 미루고 미루다 이제 올리게 된다. 오늘은 그래프의 기본 중에 기본인 용어 및 정의 정리이다.

그래프란?

먼저, 그래프란 아래의 설명과 같다.

비선형 자료구조, 즉, 트리 또한 그래프의 일종이라는 것을 알 수 있다!

이러한 그래프에는 간선의 방향성이라든가, 가중치, 부분 집합에 따라서 그래프의 종류가 나뉜다 이를 하나씩 나열해 볼 것이다.

무방향 / 방향 그래프

간선에 방향이 없고, 있고의 차이이다.

완전 그래프

정점 별로 모든 정점과 연결되어 있는 그래프를 완전 그래프라고 하는데, 이 때, 방향 완전 그래프는 무방향 완전 그래프보다 간선의 수가 2배 많다.

가중치 그래프와 부분 그래프

가중치 그래프는 간선에 가중치를 두고, 예를 들어, A에서 C로 가려면 3+1 혹은 4+5 비용이 든다고 표현할 수 있다. 부분 그래프는 말 그대로 그래프의 부분만을 그려낸 것이다.

그래프의 집합 표시

이러한 그래프를 집합 형태로 표현을 할 수 있다

그래프를 코드로 표현하기 위한 약속

그래프는 진짜 들쑥 날쑥인데 어떻게 표현하지 싶었는데, 사람들은 참 머리가 좋은 것 같다.

그래프가 어떻게 생겼든, 크기가 어떻든 정점 사이가 얼마나 멀든 좁든 간에 각 정점과 그 사이의 간선만 표현할 수 있다면, (예를 들어 어느 점과 어느 점이 어떤 선으로 연결되어 있는지 등의 정보) 오케이이다.

그 정점과 간선 등의 관계를 표현하는 방법은 위 그림에서처럼 인접 행렬, 인접 리스트가 그 방법이다. 방법은 그림으로 보는 것이 자세하고 편해서 그림으로 표현을 해 보았다.