[알고리즘] Graph

그래프

노드(Node)와 간선(Edge)으로 이루어진 자료구조

이때 노드를 정점(Vertex)라고도 말한다.

좀 더 쉽게 설명하면 노드는 도시, 간선은 도로이다.

A라는 도시(노드)에서 B라는 도시(노드)로 이동하기 위해서, A와 B를 연결하는 도로(간선)를 거친다.

 

그래프 표현 방식

인접 행렬

2차원 배열로 그래프의 연결 관계를 표현하는 방식

 

연결되어 있지 않은 노드끼리는 무한의 비용이라고 생각한다.

실제 코드에서는 논리적으로 정답이 될 수 없는 큰 값 중에서 999999999, 987654321 등의 값으로 초기화하는 경우가 많다.

 

장점

- 2차원 배열 안에 모든 정점들의 간선 정보를 담기 때문에 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠르다. (시간 복잡도: O(1))

- 구현이 쉽다.

 

단점

- 모든 정점에 대해 간선 정보를 대입해야 하므로 O(n²)의 시간복잡도를 가진다.

- 노드의 개수가 많을수록 메모리가 불필요하게 낭비된다. 

 

인접리스트

리스트로 그래프의 연결 관계를 표현하는 방식

 

모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

 

장점

- 정점들의 연결 정보를 탐색할 때 O(n)의 시간복잡도를 가진다. (n: 간선의 개수)

- 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.

 

단점

- 인접행렬에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 

- 구현이 비교적 어렵다.

 

그래프의 종류

무방향 그래프

두 정점을 연결하는 간선에 방향이 없는 그래프

방향 그래프

두 정점을 연결하는 간선에 방향이 존재하는 그래프

간선의 방향으로만 이동할 수 있다.

가중치 그래프

 두 정점을 이동할 때 간선의 기준치만큼 비용이 드는 그래프

완전 그래프

모든 정점이 간선으로 연결되어 있는 그래프

 

 

Reference

이것이 코딩테스트다 - 나동빈

https://coding-factory.tistory.com/610