[ 비선형 자료구조] 그래프

그래프

1) 개념

   그래프는 정점(vertex)와 간선(edge)으로 이루어진 대상 간의 관계를 표현하는 자료구조이다. 

 

2) 용어 정리

• 정점(vertex) / 노드 : 데이터가 저장되는 공간
• 간선(edge) / link / branch : 정점을 연결하는 선
• 인접 정점(adjacent vertex) : 직접 연결된 정점
• 단순 경로(simple path) : 방복되는 정점/간선 없이 이루어진 경로
• 차수(degree) : 무방향 그래프에서 하나의 정점에 연결된 정점의 수
• 진출 차수(out-degree) : 방향 그래프에서 정점을 기준으로 나가는 간선의 수
• 진입 차수(in-degree) : 방향 그래프에서 정점을 기준으로 들어오는 간선의 수
• 경로 길이(path length) : 경로를 구성하는 간선의 수
• cycle : 단순 경로의 시작 점과 도착점이 같은 경우

 

3) 종류

(1) 무방향 그래프(undirected graph) / 방향 그래프(directed graph)

 

• 무방향 그래프 : 간선에 방향이 없는 그래프
• 방향 그래프 : 간선에 방향이 있는 그래프

 

(2) 연결 그래프(connected graph) / 비연결 그래프(disconnected graph)

 

 

• 연결 그래프 : 무방향 그래프의 모든 정점이 간선에 의해 연결되어 있는 그래프
• 비연결 그래프 : 연결되지 않은 정점이 있는 그래프

 

(3)  완전 그래프(complete graph) 

 

• 완전 그래프 : 각 정점이 다른 모든 정점과 연결된 그래프. n개의 정점을 갖는 경우 n * (n - 1) / 2 개의 간선을 갖는다.

 

(4) 부분 그래프(subgraph)

 

• 부분 그래프 : 원래 그래프에서 일부 정점 혹은 간선을 제외한 그래프

 

(5) 가중치 그래프(weighted graph)

가중치 그래프 : 간선에 가중치가 부여된 그래프. 네트워크라고도 한다.

 

 

4) 그래프의 구현

(1) 인접 행렬을 통한 구현

  2차원 배열을 통해 각 노드가 인접 노드인지 여부를 2차원 배열의 형태로 나타낸 방식이다. 노드간 직접 연결 시 1(true), 그 외의 경우 0(false)을 테이블에 넣는다. (가중치 그래프의 경우 연결 여부를 포함한 가중치와 관련된 값을 넣을 수 있다.)

무방향 그래프의 경우

방향 그래프의 경우

 

(1 - 1) 인접 행렬의 장점

• 각 정점의 연결 여부를 확인하기가 시간복잡도 O(1)으로 매우 빠르다
• 정점의 차수(연결된 노드의 수) 파악이 O(n)으로 빠르다.
• 구현이 쉽다.

=>  밀집 그래프에 적합

 

 

(1 - 2) 인접 행렬의 단점

• 간선의 개수와 상관없이 (원소의 개수)**2 의 메모리 공간이 필요하다.
• 모든 정점의 연결 여부를 대입하는 게 O(n^2)의 시간복잡도를 갖는다.
• 각 노드의 인접 노드를 찾을 때 인접 리스트 방식과 달리 배열을 모두 순회해야 하므로 비효율적이다.

 

 

(2) 인접 리스트를 통한 구현

  인접 리스트 방식은 각 노드의 인접 노드를 리스트를 통해 표현한 방식이다. 각 정점은 인접 노드에 대한 데이터를 갖는 리스트를 가지며 리스트의 구성 순서는 일반적으로 중요하지 않다.(예외적으로 우선순위를 고려해 구현한 경우도 있다.)

 

(2 - 1) 인접 리스트의 장점

• 정점의 연결 여부 탐색이 O(n) 시간이면 충분하다.
• 각 리스트가 인접 노드로 구성되기 때문에 인접노드 탐색이 쉽다.
• 인접 행렬과 달리 필요한 메모리 공간만 사용하므로 효율적이다.

=> 희소 그래프에 적합

 

 

(2 - 2) 인접 리스트의 단점

• 임의의 두 정점의 연결 여부 확인할 때 인접 행렬의 경우에 비해 비효율 적이다.
• 리스트 구현이 까다롭다.
• 간선이 많아질수록 필요한 메모리 공간이 증가한다.

 

그래프의 탐색에 쓰이는 알고리즘은 아래 글에 정리해 두었다.

그래프의 탐색 - BFS, DFS