C로 만드는 자료구조 - 그래프(Graph)란?

그래프(Graph)란?

 그래프는 객체 사이의 연결 관계를 표현하는 자료구조이다. 지금까지 설명한 자료구조 중에서 가장 현실 세계의 다양한 문제들을 효과적으로 모델링 할 수 있을 정도로 표현 능력이 매우 우수하다.

 다음 그림은 우리나라의 고속도로 지도이다. 각 도시를 연결하는 고속도로를 자료구조로 나타낼 수 있을까?

 앞서 소개한 자료구조 중에서 선형 자료인 리스트,스택,큐 같은 경우는 객체들의 선,후 관계 밖에 나타내지 못하기 때문에 1:1인 관계가  아닌 것이 존재하는 고속도로를 표현하기에는 적합하지 못하다. 하나의 객체가 여러개의 객체와의 관계를 나타낼 수 있는 자료구조인 트리는 부모 자식 간의 관계만 나타낼 수 있고 일반적인 관계는 나타내지 못한다는 한계가 있다. 각 도시를 연결하는 고속도로 같은 경우는 각 도시와의 관계가 부모-자식 관계가 아닌 순환구조가 만들어 질 수도 있기 때문에 트리를 사용하는 것도 적합하지 못하다.

그래프의 개념

 

 그래프는 노드(Node 또는 정점 Vertex)와 간선(Edge)의 집합이다. 노드는 일반적으로 객체를 나타내며, 간선은 이러한 객체 사이의 관계를 정의한다. 고속도로 예시에서 각 도시는 그래프의 노드들이 되고 도시들을 연결하는 고속도로는 간선이 된다. 

이러한 그래프의 정의는 다음과 같이 노드V와 간선E로 구성된 그래프 G에 대한 식으로 나타낼 수 있다.

G= (V(G),E(G)) = (V,E)

 위 식은 “그래프 G는 노드들의 집합 V(G)와 간선들의 집합 E(G)로 구성된다.” 라는 의미로 그래프 G의 노드를 V, 그래프 G의 간선을 E로 표현하기도 한다. 일반적으로 간선의 특성에 따라 그래프의 종류가 구분되며, 다음은  그래프의 종류를 정리한 표이다.

구분	종류	설명
간선의 방향성	무방향 그래프	간선에 방향이 없는 그래프
	방향 그래프	간선에 방향이 있는 그래프
간선의 가중치	가중 그래프	간선에 가중치가 할당된 그래프
구조적 특징	완전 그래프	연결가능한 최대 간선 수를 가진 그래프
	부분 그래프	원래의 그래프에서 일분의 노드나 간선을 제외하여 만든 그래프
	다중 그래프	중복된 간선을 포함하는 그래프

- 각 그래프에 대한 자세한 설명은 다음 글에서 자세히 다루려고 한다.

그래프의 추상 자료형

 그래프 사용에 필요한 기본 연산을 정리한 그래프의 추상 자료형(ADT:Abstract Data Type)을 표로 정리했다. 

이름		입력 값	출력 값	설명
그래프 생성	createGraph()	최대 노드 개수 n	그래프 g	최대 n개의 노드를 가지는 그래프 g 생성
그래프 삭제	deleteGraph()	그래프 g	N/A	그래프 g의 모든 노드와 간선을 제거
노드 추가	addVertex()	그래프 g 노드 v	N/A	새로운 노드 v를 그래프 g에 추가
간선 추가	addEdge()	그래프 g 노드 u 노드 v	N/A	노드 u와 v를 연결하는 새로운 간선 e를 그래프 g에 추가
노드 제거	removeVertex()	그래프 g 노드 v	N/A	그래프 g의 노드 v와 v와 부속된 모든 간선들을 제거
간선 제거	removeEdge()	그래프 g 노드 u 노드 v	N/A	그래프 g의 노드 u,v 를 연결하는 간선 제거
인접 노드 반환	adjacentNode()	그래프 g 노드 v	노드의 목록	그래프 g에서 노드 v에 인접한 모든 노드들 반환

 주의해야 할점은 간선 추가/제거 시에 입력 노드가 2개의 순서이다. 만약 무방향 그래프라면 두 입력 노드의 순서는 바뀌어도 상관이 없지만 방향 그래프라면 순서가 매우 중요해 진다. 방향 그래프에서 순서가 바뀌면 전혀 다른 간선이 되기 때문이다. 따라서 방향 그래프 일때 간선 추가/제거 시에는 시작 노드와 종료 노드의 순서를 신경 써야 한다.