[그래프] 그래프 알고리즘 기초

그래프

그래프: 정점(Node, Vertex)과 간선(Edge)으로 나타내는 자료구조의 한 종류

 

그래프 알고리즘의 포인트: "어떠한 문제 상황을 어떻게 그래프로 만들어낼 것인가"

 

경로(Path): 정점 A에서 B로 가는 경로

사이클(Cycle): 정점 A에서 다시 A로 돌아오는 경로

 

단순 경로/단순 사이클

같은 정점을 두 번 이상 방문하지 않는 경로/사이클

특별한 언급이 없다면, 일반적으로 말하는 경로/사이클은 단순 경로/사이클이다.

 

그래프의 종류

- 방향이 있는 그래프

- 방향이 없는 그래프(양방향 그래프)

알고리즘 상에서 방향이 없는 그래프는 모두 방향이 있는 그래프로 바꿔서 저장해야한다.

- 간선이 여러개인 경우'

일반적으로 잘 없는 경우이지만, 필요한 간선을 제외하고 삭제하면 된다.

ex) 최단 거리를 구하는 경우 가중치가 짧은 것 빼고 긴 것은 삭제하면 됨.

- 루프: 자기 자신으로 돌아오는 간선

- 가중치: 가중치가 없는 경우 1로 계산하면 된다.

- 차수(Degree): 정점과 연결되어 있는 간선의 개수

In-degree/Out-dgree 를 이용해 sns 팔로우, 지하철 노선 등을 표현한다

 

그래프의 표현

그래프의 저장 방법으론 크게 1. 인접행렬 2. 인접리스트가 있다.

 

1. 인접행렬

정점의 개수가 V인 경우, V X V 크기의 이차원 배열을 이용한다

A[i][j] = 간선이 없는 경우 0, 있는 경우 1(혹은 가중치)

공간복잡도: O(V^2)

시간복잡도: O(V)

 

2. 인접리스트

크기를 동적으로 변경할 수 있는 리스트를 사용해 구현한다.

- 가중치가 없는 경우

연결된 노드를 저장

A[1] 2 5

A[2] 1 3 4 5

A[3] 2 4

 

-가중치가 있는 경우

연결된 노드와 가중치를 저장

A[1] (2, 2) (5, 7)

A[2] (1, 2) (3, 2) (4, 3)

A[3] (2, 2) (4, 1)

 

공간복잡도: O(E)

시간복잡도: O(차수)

 

그래프에서의 효율이란 한 정점 X와 연결된 간선을 효율적으로 찾는 방법

인접 행렬에 비해 인접 리스트의 효율이 좋기 때문에 보통 인접 리스트를 활용한다.

인접 행렬이 뛰어난 유일한 경우는 두 정점 사이에 간선이 있는지 없는 지 구하는 경우.

 

그 외 표현방법으로 간선리스트가 있는데,

1. 라이브러리를 사용하지 못하는 환경에서

2. Linked List를 구현하기 싫은 경우

사용한다.