Graph 그래프

알아보기

정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다.
정점은 노드, 간선은 노드를 연결하는 선으로 생각하면 된다.
그렇다고 해서 노드 간 부모 자식이라는 관계는 존재하지 않고 그냥 연결관계만 나타낸다.
Tree와 비슷하지만, 그래프는 간선이 없는 노드도 존재한다는 점에서 차이를 나타낸다.

탐색방법

그래프 탐색이란 하나의 정점으로 부터 모든 정점들을 한번씩 방문하는 행위를 뜻한다.

예를 들어 섬끼리 이동할 수 있을지, 이동할 수 있다면 시간이 얼마나 걸리는지 등의 예시에서 사용될 수 있다.

어떤식으로 방문해야 할까?

여기서 두가지 방법이 있다.
DFS 깊이 우선 탐색
BFS 너비 우선 탐색

구현

인접 행렬과 인접리스트 방식으로 구현할 수 있다.

인접행렬

<장점>
2차원 배열 안에 모든 정점들의 간선 정보가 담겨있어, O(1)의 시간복잡도를 가진다.
구현 간단.
<단점>
간선 정보를 대입시 O(n^2)의 시간복잡도를 가진다.
2차원 배열 생성이 필수이므로 공간 낭비가 있다.

인접리스트

그래프의 정점 관계를 리스트로 표현.
정점 개수 만큼 배열 생성 한 뒤, 각 정점과 연결된 정점들을 리스트에 담는다.
<장점>
연결 정보 탐색시 O(n) 시간 복잡도
공간낭비가 적다.
<단점>
배열보다 리스트가 탐색 속도가 느리므로 시간이 오래걸린다.
배열보다 구현이 복잡하다.

그래프의 종류

방향성의 유무, 가중치의 유무에 따라 그래프의 종류가 나뉜다.

인접행렬로 각 그래프를 표현해 보았다.

무방향 그래프

(a,b) (b,a) 모두 1로 체크하여 연결을 나타내준다.

양방향 그래프

a -> b 일때 (a,b) = 1 로 체크하여 방향성을 나타내준다.

가중치 그래프

방향성 그래프 개념에 가중치의 값을 넣어준다.