[자료구조] Graph 컨셉, 종류

Graph는 연결되어 있는 원소들 사이의 다대다 관계를 표현하는 비선형 자료구조로서, 버스노선도나 지하철 노선도와 같이 여러 원소들이 맞물려 있는 경우에 사용하는 자료구조형이다.

 

그래프는 두개의 집합 V와 간선 E로 구성되어 있다. 표기는 G = (V,E)로 한다.

 

그래프는 무방향 그래프와 방향그래프, 부분그래프, 가중 그래프로 나눌 수 있다.

무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프로서, 간선을 나타내는 쌍에 순서가 없다. 즉 간선을 통해서 양방향으로 갈 수 있는 그래프이다.

방향 그래프는 모든 간선이 방향을 가지는 그래프로서, 방향은 정점의 쌍 <u,v>의 정점의 순서로 표시한다. 간선을 통해서 한 쪽 방향으로만 갈 수 있다.

부분그래프는 원래의 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프로서, 필요한 부분만 보고 싶을 때 사용된다.

가중 그래프는 정점을 연결하는 간선에 가중치를 할당한 그래프이다.