그래프(Graph)의 종류

용어	설명
그래프(Graph)	노드와 간선을 하나로 모아 놓은 자료 구조
정점(Vertex)	노드라고도 하며, 정점에는 데이터가 저장된다.
간선(Edge)	링크라고도 하며, 노드간의 관계를 나타낸다.
인접 정점 (adjacent vertex)	간선에 의해 직접 연결된 정점
차수(degree)	무방향 그래프에서 하나의 정점에 인접한 정점의 수. 무방향 그래프에 존재하는 존재하는 정점의 모든 차수의 합 == 그래프의 간선의 수 * 2
진출 차수 (out-degree)	방향 그래프에서 사용되는 용어로, 현재 노드에서 외부로 향하는 간선의 수 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 == 방향 그래프의 간선의 수
진입 차수 (in-degree)	방향 그래프에서 사용되는 용어로, 외부 노드에서 현재 노드로 들어오는 간선의 수
단순 경로 (simple-path)	경로 중 반복되는 정점이 없는 경우
경로 길이 (path-length)	경로를 구성하는데 사용된 간선의 수
사이클(cycle)	단순 경로의 시작 정점과 종료 정점이 동일한 경우
연결 요소 ★ (component)	하나의 컴포넌트 안에 속한 정점은 서로 모두 이어져 있다.  다른 컴포넌트끼리는 이어져 있지 않다. 컴포넌트는 항상 최대의 크기이다.

 

[ 그래프의 종류 ]

01. 무방향 그래프 (Non-Directed Graph)

• 무방향 그래프의 간선은 간선을 통해서 양 방향으로 이동할 수 있다.

02. 방향 그래프 (Directed Graph)

• 간선의 방향성이 존재하는 그래프이다. 방향 그래프의 간선은 주어진 방향으로만 이동할 수 있다.

03. 가중치 그래프 (Weighed Graph)

• 두 정점을 연결하는 간선에 비용이나 가중치가 할당된 그래프
• 네트워크라고도 한다.

04. 완전 그래프 (Complete Graph)

• 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
• 정점의 수를 n이라고 할 때, 간선의 수는 n * (n-1) / 2이다.

05. 다중 그래프 (Multi Graph)

• 두 정점 사이에 두 개 이상의 간선이 연결되어 있는 그래프

06. 부분 그래프 (Sub Graph)

• 기존 그래프에서 특정 간선을 제외하여 만든 그래프 
• 아래 그림에서 G2는 G1의 부분 그래프이다.

07. 연결 그래프 (Connected Graph)

• 무방향 그래프에 있는 모든 정점 쌍에 대해서 항상 경로가 존재하는 그래프
• 컴포넌트가 단 하나인 경우이다.
• 예를 들어 트리(Tree)는 사이클이 없는 연결 그래프이다. 

08. 비연결 그래프 (Disconnection Graph)

• 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 그래프

09. 순환 VS 비순환 그래프 (Disconnection Graph)

• 사이클을 가지고 있으면 순환 그래프이고, 그렇지 않으면 비순환 그래프이다.

10. 희소 VS 밀집 그래프 (Disconnection Graph)

• 희소 그래프는 노드수보다 간선의 수가 적은 그래프이다. 
  • 보통 간선의 수가 |V|log|V|보다 적을 경우를 희소 그래프라고 한다.
• 밀집 그래프는 노드 수보다 간선의 수가 더 많은 그래프이다.

 

[ 그래프의 표현 ]

그래프를 표현하는 방법으로는 다음의 세가지 경우가 존재하는데 각 경우의 수와 장,단점을 알아보자.

1. 에지 리스트(Edge List) 방식

• 에지를 중심으로 그래프를 표현한다.
• 무향이라면 (1, 2)와 (2, 1)은 같은 표현이다.
• 배열에 출발노드, 도착노드, (가중치)를 저장하여 에지를 표현한다. 
• 가중치가 있는 그래프는 행을 3개로 추가하여 가중치도 함께 저장하면 된다.
• 벨만 포드나 크루스칼 알고리즘에 사용한다.

장점

• 구현이 쉽다.

단점

• 특정 노드와 관련되어 있는 에지를 탐색하기 어렵다.

에지리스트로 그래프 표현하기

 

2. 인접 행렬(Adjacency Matrix) 방식

• 2차원 배열을 사용하여 그래프를 표현한다. 
• 노드 중심으로 그래프를 표현한다.
• 배열에 값이 있다면 에지가 존재한다는 뜻이고, 가중치 그래프라면 가중치를, 아니라면 1을 표현한다.

장점

• 구현이 쉽다.
• 두 노드를 연결하는 에지의 여부와 가중치 값은 배열에 직접 접근하면 바로 확인할 수 있다.
• N번의 접근으로 해당 정점의 차수를 알 수 있다. 

단점

• 노드와 관련된 에지를 탐색하려면 N번의 접근이 필요하기 때문에(모든 노드를 전부 순회해야 한다.) 노드의 개수에 비해 에지가 적을 때는(희소그래프) 공간 효율성이 떨어진다.
• 노드 개수가 너무 많은 경우에는 힙스페이스 로 인해 2차원 배열을 선언 자체를 할 수 없다.

 

3. 인접 리스트(Adjacency List) 방식

• 그래프의 노드들을 리스트로 표현한 것 
• 각 정점에 인접한 인접 정점들을 리스트의 요소로 저장한다.
• 실제 코딩테스트에서 가장 많이 사용한다.

장점

• 노드와 연결되어 있는 에지를 탐색하는 시간이 매우 빠르다.
• 노드 개수가 많아도 공간 효율아 좋아서 메모리 초과 에러가 발생하지 않는다. 

단점

• 다른 방법에 비해 구현이 복잡하다. 
• 정점 i의 리스트에 있는 노드의 수, 즉 정점의 차수(간선의 개수)만큼의 시간이 필요하다.