그래프

그래프

비선형적 자료구조. 

회사 조직도와 같은 계층을 표현한다던가 친구 관계도를 표현하는 것처럼 말이다.

 

그래프(graph)는 관계에 특화된 자료구조로 정점(Vertex)과 간선(Edge)으로 구성되어 있다.

각 정점은 고유하게 식별되는 객체이고, 간선은 정점 간의 관계를 표현한다.

 

종류

그래프의 종류에는 간선이 방향성을 가는것으로 그래프를 판단해서 알수있는 방향 그래프와 무방향 그래프로 구분할수있으며 간선이 단순 연결 이상의 정보를 가지는 가중치 그래프도 있다.

 

 

용어

정점끼리는 인접(Adajcent)하다고 한다.

부속(Incident)되어 있다고 한다.

정점에 부속되어 있는 간선의 수를 차수(Degree)라고 하며 정점으로 들어오는 방향인지,

나가는 방향인지 구분해 진입 차수(In-degree), 진출 차수(Out-degree)로 말할 수 있다.

 

한 정점에서 다른 정점까지 간선으로 연결된 정점을 순서대로 나열한 리스트를 경로(Path)라 한다.

경로를 구성하는 간선 수를 경로 길이(Path length)라 한다.

모두 다른 정점으로 구성된 경로를 단순 경로라 한다.

단순 경로 중 경로의 시작 정점과 마지막 정점이 같은 경로를 사이클이라 한다.

경로가 있으면 정점끼리 연결*(Connected) 되었다고 한다.

 

표현

인접 행렬

 

 

정점이 N개 있을 경우 N x N 크기의 2차원 배열로 그래프를 표현할 수 있다. 배열의 원소는 간선의 가중치를 나타내게 된다. 가령 edges[i][j] 는 정점 i 에서 j로 가는 간선을 나타낸 것이다. 2차원 배열을 사용하기 때문에 그래프에 간선이 적다면* 그만큼 메모리를 낭비하게 된다.

 

인접 리스트

 

인접 리스트는 각 정점에 연결된 정점의 ID만 저장하는 방식으로 그래프를 표현하는 것이다.

 

순회

한 정점에서 시작해 그래프에 있는 모든 정점을 한 번씩 방문하는 것을 그래프 순회(Graph Traversal) 또는 탐색(Search)이라 한다. 이러한 방법에는 깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search)이 있다.

 

깊이 우선 탐색은 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속하는 방법으로 스택을 사용한다. 

너비 우선 탐색은 시작 정점에 인접한 정점을 모두 차례로 방문하고 나서 방문했던 정점을 시작으로 다시 인접한 정점을 차례로 방문하는 방식으로 큐를 사용한다.