[자료구조] 그래프 (Graph)

 

 

목차

 

그래프란?

그래프는 정점과 간선으로 이루어진 자료구조임. 

→ 트리는 그래프의 일종인데 다만 트리와는 달리 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며, 루트 노드, 부모와 자식이라는 개념이 존재하지 않음.

G = (V, E)

V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미함.

 

그래프에서 사용하는 용어

- 정점(vertice) : 노드(node)라고도 하며 정점에는 데이터가 저장됨 (0, 1, 2, 3)

- 간선(edge): 노드 간의 관계를 나타냄

- 인접 정점(adjacent vertex) : 간선에 의해 연결된 정점 EX) 정점 0과 정점 1은 인접 정점)

- 단순 경로(simple-path): 경로 중 반복되는 정점이 없는 것, 같은 간선을 지나가지 않는 경로

- 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (정점 0의 차수는 3)

- 진출 차수(out-degree) : 방향 그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수

- 진입 차수(in-degree) : 방향 그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수

- 경로 길이 (path length) : 경로를 구성하는 데 사용된 간선의 수

- 사이클 (cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

 

그래프 표현 방법

V(G1) = {0, 1, 2, 3}, E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}

V(G2) = {0, 1, 2, 3}, E(G2) = {(0, 1), (0, 2)}

V(G3) = (0, 1, 2}, E(G3) = {<0, 1>, <1, 0>, <1, 2>}

 

그래프 ADT

객체 : 정점의 집합과 간선의 집합

연산:

create() : 그래프 생성

insertVertex(v) : 그래프에 정점 v 삽입

insertEdge(u, v) : 그래프에 u정점과 v정점을 연결하는 간선 삽입

deleteVertex(v) : 그래프에서 정점 v 삭제 (v에 연결된 모든 간선도 함께 삭제)

deleteEdge(u, v) : 그래프에서 u정점과 v정점을 연결하는 간선 삭제

adjacent(v) : 정점 v에 인접한 모든 정점을 반환

 

 

그래프 구현 방법

인접 행렬 (Adjacency Matrix)과 인접 리스트 (Adjacency List). 보통은 인접 리스트 많이 씀.

인접 행렬은 N 제한이 적을 때 사용한다.

인접 리스트 : 배열을 정점 개수만큼 잡아주고, 정점이 이어질 때마다 하나씩 추가해준다.

 

인접 행렬 방식

인접 행렬은 그래프의 노드를 2차원 배열로 만든 것임.

정점을 연결하는 노드에 다른 노드들이 인접 정점이면 1, 아니면 0을 넣어줌.

 

EX) 

정점의 개수가 n이라면 n*n 형태의 2차원 배열이 인접 행렬로 사용된다.

인접 행렬에서 행과 열은 정점을 의미하며, 각각의 원소들은 정점 간의 간선을 나타낸다.

무방향 그래프는 (a), (b)에서 볼 수 있듯이 인접 행렬이 대칭적 구조를 가진다.

(두 개의 정점에서 간선이 동시에 연결되어 있기 때문)

가중치 그래프의 경우 행렬에서 0과 1이 아니라 각 간선의 가중치 값이 저장된다.

(이 경우 가중치가 0인 것과 간선이 없는 것이 구별돼야 함)

 

인접 행렬 장점

1. 2차원 배열 안에 모든 정점들의 간선 정보를 담기 때문에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 때 O(1)의 시간 복잡도면 가능함.

2. 구현이 비교적 간편함.

3. 정점(i)의 차수를 구할 때는 다음과 같이 인접 행렬(M)의 i번째 행의 값을 모두 더하면 되므로 O(n)의 시간 복잡도를 가진다.

 

인접 행렬 단점

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

2. 무조건 2차원 배열이 필요하기에 필요 이상의 공간이 낭비됨.

 

 

인접 리스트 방식

인접 리스트는 그래프의 노드들을 리스트로 표현한 것임. 주로 정점의 리스트 배열을 만들어 관계를 설정하며 노드들 간에 직접 연결이 되어있으면 해당 노드의 인덱스에 그 노드를 삽입해주면 된다.

무방향 그래프의 경우 간선이 추가되면 각각의 정점의 인접 리스트에 반대편 정점의 노드를 추가해야 한다.

 

인접 리스트 장점

1. 정점들의 연결 정보를 탐색할 때 O(n)의 시간이면 가능함. (n: 간선의 개수)

2. 필요한 만큼의 공간만 사용하기 때문에 공간의 낭비가 적음.

 

인접 리스트 단점

1. 특정 두 점이 연결되었는지 확인하려면 인접 행렬에 비해 시간이 오래 걸림 (배열보다 search 속도 느림)

2. 구현이 비교적 어려움

 

인전 행렬 VS 인접 리스트

약 10억 개의 노드가 있고 각 노드가 2개씩의 간선만 있는 상황이다. 인접 행렬로 구현한 그래프에서는 한 정점의 차수를 구할 때 10억 번의 연산을 수행할 것이다. 반면, 인접 리스트로 구현한 그래프에서는 2번의 연산만 수행하면 된다.