알고리즘 기본기 다지기7.기초 데이터구조 (그래프)

그래프(Graph)

그물 망들은 많은 정점과 정점 사이의 간선들로 구성되어져 있다. 그래프는 이러한 그물망처럼 얽힌 정점과 간선으로 이루어진 데이터 모델이다. 

그래프는 풍부한 표현력을 가진 자료형인만큼 파생되는 개념, 원리, 용어, 알고리즘이 풍부하다.

그래프 종류

•  방향그래프(directed graph) : 방향 간선(directed edge)라는 방향을 갖은 간선들로 이루어진 그래프이다. 대표적으로 일상생활에서 항공편이 있다. 순서를 가진 (u,v)로 표현되며, 정점 u는 시점(origin), 정점 v는 는 종점(destination)을 나타낸다.
• 무방향그래프(undirected graph) : 정점들의 무순쌍(u,v)으로 표현된다. 대표적으로 항로가 있다. 항로 존재하나 방향이 정해져있지 않다. 

그래프 용어

정점(vertex) : 그래프에서의 노드

간선(edge) : 노드 간의 연결선

차수(degree) : 정점에 연결된 간선의 수

루프(self-loof, loop) : 양 끝점이 동일한 간선

인접(adjacent) : 간선 한 개를 사이에 두고 이웃한 점점

경로(path) : 정점과 간선의 교대열, 정점으로 시작하여 정점으로 끝난다.

그래프의 속성

그래프 모든 정점의 차수 합 = 간선의 수 * 2

무방향 그래프의 간선 상산 수 = 무방향 그래프의 정점 수 ( 무방향 그래프의 정점 수 - 1) / 2

그래프 구현

간선리스트 구조(Edge List)

각 정점의 노드를 가리키는 포인터를 저장한 리스트와 간선 노드들을 가리키는 포인터를 저장한 간선리스트로 구성된다.

가장 단순하며 기억장소 사용 면에서 유리하지만, 성능상에 문제가 있다.

인접한 정점을 확인하려면 모든 간선을 검사해야한다.

인접리스트 구조(Adjacency List)

간선리스트 구조의 단점을 보완하는 구현방식이다. 간선리스트 구조 + 데이터 구조가 추가된다. 각 정점마다 부착리스트가 있으며 간선 노드에 대한 참조리스트를 가진다.

인접행렬(Adjacency Matrix)

간선리스트 구조의 단점을 보완하는 구현방식이다. n X n 배열로서 배열의 원소는 행과 열에 교차하는 인접 정점들 사이의 간선 노드에 대한 참조를 저장한다. 인접 정점들에 대해서는 널을 저장한다.

참조

알고리즘 국형준
https://ko.wikipedia.org/wiki/%EB%8D%B1_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)