그래프란 정점과 간선으로 구성된 자료구조
일반적으로 G = (V,E) 로 나타내는데, V
•
V : vertices , 정점
•
E : edges , 간선
•
|V| : 정점의 개수
•
|E| : 간선의 개수
그래프는 간선의 종류에 따라 2가지로 구분할 수 있다.
그리고 그 종류에서도 그래프의 특징으로 종류를 더 세분화할 수 있다.
그래프의 종류
그래프는 간선의 종류로 크게 2가지로 나뉜다.
•
무향 그래프 (undirected graph)
•
유향 그래프 (directed graph)
그래프의 간선에 방향이 있고 없고의 차이를 보여준다.
무향 그래프
간선에 방향이 존재하지 않는다. 1 → 4 또는 4 → 1의 이동이 모두 가능한 그래프다.
이 그래프의 간선을 표시할 때 보통 (1 , 4) 와 같이 표시하는데, 순서가 정해지지 않는 pair가 된다. 따라서 (1 , 4) 나 (4 , 1)이나 같은 간선을 의미한다.
유향 그래프
간선에 방향성이 생긴 그래프다. 무향그래프와 다르게 (1 , 4) 와 (4 , 1)은 서로 다른 간선을 나타내게 된다. 간선이 방향성을 갖기 때문에 순서가 곧 방향성을 나타내기 떄문이다. 따라서 유향 그래프는 순서가 정해진 pair가 된다.
일반적으로 무향 그래프보다는 유향 그래프에서 자주 쓰이는 추가적인 그래프의 옵션이 있는데, 그래프의 간선에 가중치가 존재하는 경우를 가중치 그래프라고 한다. 가중치는 보통 이동할 때 걸리는 시간, 비용 등으로 대표가 되어서 최단거리, 최소비용으로 이동하는 경로를 찾을 때 사용된다.
그래프의 용어
그래프에서 사용되는 용어가 몇가지 존재한다.
•
인접 정점(adjacent vertices)
•
차수 (degree)
•
사이클 (cycle)
인접정점
차수
사이클
구현 방법
그래프의 구현 방법은 총 3가지가 있다.
•
간선 리스트
•
인접 리스트
•
인접 행렬
이렇게 3가지 종류로 구현이 가능하다. 보통 알고리즘 문제를 풀 때는 편의를 위해서 인접 리스트와 인접 행렬 방식을 많이 사용한다. 실제로 간선 리스트 방식은 좀 오래된 그래프 표현 방식이다.
그래프의 구현은 생각보다 간단하다. 구성은 정점과 간선이지만 우리가 실제로 그래프로 인식하는 이유는 간선이 생성되기 때문이다. 즉 그래프를 구성할 때는 간선을 저장하면 그것이 결국 그래프가 되는 것이다.
아래 그래프를 기준으로 각 구현방법을 설명해본다.
간선 리스트
인접 리스트
인접 행렬
그래프 구현
간선 리스트는 자주 활용하지 않으므로 생략하고 인접 리스트 방식만 설명한다.
인접 행렬은 그냥 단순히 정적 2차원 배열로 만들면 된다.
인접 리스트
인접 행렬