[Data Structure] 그래프 (Graph)

Computer Science / Data Structure

자료 구조 중 하나인 그래프에 대한 이해를 위한 정리

게시 2024.07.22 업데이트 2024.07.24

Graph Image

By Hyung-Jin Han

약 17분 소요

그래프(Graph)의 개념

단순히 노드(n, node)와 그 노드를 연결하는 간선(e, edge)을 하나로 모아 놓은 자료 구조로,

즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다.
- ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목 등…
그래프는 여러 개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수 있다.

그래프(Graph)의 특징

그래프는 네트워크 모델이다.
2개 이상의 경로가 가능하다.
- 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
- self-loop 뿐만 아니라 loop/circuit 모두 가능하다.
- 루트 노드라는 개념이 없다.
- 부모-자식 관계라는 개념이 없다.
- 순회는 DFS¹나 BFS²로 이루어진다.
- 그래프는 순환(Cyclic) 또는 비순환(Acyclic)이다.
- 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
- 간선의 유무는 그래프에 따라 다르다.

그래프(Graph)의 종류

무방향 그래프 VS 방향 그래프

무방향 그래프 (Undirected Graph)
무방향 그래프의 간선은 간선을 통해서 양방향으로 갈 수 있다.
정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
- (A, B)는 (B, A)와 동일
ex) 양방향 통행 도로
방향 그래프 (Directed Graph)
간선에 방향성이 존재하는 그래프
A → B로만 갈 수 있는 간선은 <A, B>로 표시한다.
- <A, B>와 <B, A>는 다름
ex) 일방 통행

가중치 그래프 (`Weight Graph`)

간선에 비용이나 가중치가 할당된 그래프로, 네트워크(Network)라고도 한다.

ex) 도시-도시 간의 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등

연결 그래프 VS 비연결 그래프

연결 그래프 (Connected Graph)
무방향 그래프에 있는 모든 정점의 쌍에 대해서 항상 경로가 존재하는 경우를 말한다.
ex) 트리 (Tree)³
비연결 그래프 (Disconnected Graph)
무방향 그래프에서 특정 정점의 쌍 사이에 경로가 존재하지 않는 경우를 말한다.

사이클 VS 비순환 그래프

사이클 (Cycle)
단순 경로(Simple Path)⁴의 시작 정점과 종료 정점이 동일한 경우를 말한다.
비순환 그래프 (Acyclic Graph)
사이클이 없는 그래프

완전 그래프 (`Complete Graph`)

그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프이다.

무방향 완전 그래프
정점의 수가 $n$이면 간선의 수 : $n \times (n - 1) / 2$

그래프(Graph)의 구현 2가지

1. 인접 리스트 (`Adjacency List`)

인접 리스트(Adjacency List)로 그래프를 표현하는 것이 가장 일반적인 방법이다.

모든 정점(혹은 노드)을 인접 리스트에 저장하는 것, 즉, 각각의 정점에 인접한 정점들을 리스트로 표시한 것이다.

배열(혹은 해시 테이블)과 배열의 각 인덱스마다 존재하는 또 다른 리스트(배열, Array List⁵, Linked List⁶)를 이용해서 인접 리스트를 표현
1 2 3 4 5 6 7 0: 1 1: 2 2: 0, 3 3: 2 4: 6 5: 4 6: 5
- 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 리스트에 쉽게 접근할 수 있다.

무방향 그래프 (Undirected Graph)에서 (A, B) 간선은 두 번 저장된다.

한 번은 A 정점에 인접한 간선을 저장하고, 다른 한 번은 B에 인접한 간선을 저장한다.
정점의 수가 $n$, 간선의 수가 $e$인 무방향 그래프의 경우
- $n$개의 리스트, $n$개의 배열, $2e$개의 노드가 필요

트리(Tree)³에서는 특정 노드 하나(로트 노드)에서 다른 모든 노드로 접근이 가능 → Tree 클래스 불필요

그래프에서는 특정 노드에서 다른 모든 노드로 접근이 가능하지는 않음 → Graph 클래스 필요

  
class Graph {
  public nodes: Node[];
}
// 트리의 노드 클래스와 동일
class Node {
  public name: string;
  public children: Node[];
}

2. 인접 행렬 (`Adjacency Matrix`)

인접 행렬은 NxN 불린 행렬(Boolean Matrix)로써 matrix[i][j]가 true라면 i → j로의 간선이 있다는 뜻이다.

0과 1을 이용한 정수 행렬(Integer Matrix)을 사용할 수도 있다.

  
if(간선 (i, j)가 그래프에 존재) {
  matrix[i][j] = 1;
} else {
  matrix[i][j] = 0;
}

정점(노드)의 개수가 $n$인 그래프를 인접 행렬로 표현
- 간선의 수와 무관하게 항상 $n^2$개의 메모리 공간이 필요하다.
무방향 그래프를 인접 행렬로 표현한다면, 이 행렬은 대칭 행렬(Symmetric Matrix)이 된다.
- 물론 방향 그래프는 대칭 행렬이 안 될 수도 있다.
인접 리스트를 사용한 그래프 알고리즘들(ex. 너비 우선 탐색) 또한 인접 행렬에서도 사용이 가능하다.
- 하지만 인접 행렬은 다소 효율성이 떨어진다.
- 인접 리스트는 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있지만, 인접 행렬에서는 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다.

인접 리스트와 인접 행렬 중 선택 방법

인접 리스트

그래프 내에 적은 숫자의 간선 만을 가지는 희소 그래프(Space Graph)의 경우

장점

어떤 노드에 인접한 노드들을 쉽게 찾을 수 있다.

그래프에 존재하는 모든 간선의 수는 $O(n + e)$ 안에 알 수 있다.

즉, 인접 리스트 전체를 조사한다.

단점

간선의 존재 여부와 정점의 차수에 따라 시간이 필요하다.

즉, 정점 i의 리스트에 있는 노드의 수, 즉, 정점 차수만큼의 시간이 필요

인접 행렬

그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우

장점

두 정점을 연결하는 간선의 존재 여부(matrix[i][j])를 $O(1)$ 안에 즉시 알 수 있다.

정점의 차수는 $O(n)$ 안에 알 수 있다.

즉, 인접 배열의 i번 째 행 또는 열을 모두 더한다.

단점

어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야 한다.

그래프에 존재하는 모든 간선의 수는 $O(n^2)$ 안에 알 수 있다.

즉, 인접 행렬 전체를 조사한다.

그래프(Graph)의 탐색

일반적인 방법으로는, 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search) 두 가지가 있다.

1. 깊이 우선 탐색 (DFS, Depth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 방식이다.
모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
- 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하게 구현이 가능하다.

2. 너비 우선 탐색 (BFS, Breadth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 방식이다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
- ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후, Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
  - 깊이 우선 탐색의 경우 → 모든 친구 관계를 다 살펴봐야 할지도 모른다.
  - 너비 우선 탐색의 경우 → Ash와 가까운 관계부터 탐색한다.

같이 보기

그래프(Graph)와 관련된 용어

정점 (vertex)
- 위치라는 개념 (node라고도 부름)
간선 (edge)
- 위치 간의 관계
- 즉, 노드를 연결하는 선 (link, branch라고도 부름)
인접 정점 (adjacent vertex)
- 간선에 의해 직접 연결된 정점의 수
정점의 차수 (degree)
- 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- $무방향 \ 그래프에 \ 존재하는 \ 정점의 \ 모든 \ 차수의 \ 합 = 그래프의 \ 간선 \ 수의 \ 2배$
진입 차수 (in-dgree)
- 방향 그래프에서 외부에서 오는 간선의 수 (내차수라고도 부름)
진출 차수 (out-degree)
- 방향 그래프에서 외부로 향하는 간선의 수 (외차수라고도 부름)
- $방향 \ 그래프에 \ 있는 \ 정점의 \ 진입 \ 차수 \ 또는 \ 진출 \ 차수의 \ 합 = 방향 \ 그래프의 \ 간선의 \ 수$
  - $내차수 + 외차수$
경로 길이 (path length)
- 경로를 구성하는 데 사용된 간선의 수
단순 경로 (simple path)
- 경로 중에서 반복되는 정점이 없는 경우
사이클 (cycle)
- 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프(Graph)와 트리(Tree)의 차이

정의

그래프 (Graph)
노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료 구조
트리 (Tree)
DAG⁷의 그래프의 한 종류

방향성

그래프 (Graph)
방향 그래프(Directed)와 무방향 그래프(Undirected) 모두 존재
트리 (Tree)
방향 그래프(Directed)

사이클

그래프 (Graph)
사이클(Cycle)과 자체 간선(self-loop) 모두 가능하며, 순환 그래프(Cyclic)와 비순환 그래프(Acyclic) 모두 존재
트리 (Tree)
사이클(Cycle)과 자체 간선(self-loop) 모두 불가능하며, 비순환 그래프(Acyclic)

루트 노드

그래프 (Graph)
루트 노드의 개념이 없음
트리 (Tree)
한 개의 루트 노드만이 존재하며, 모든 자식 노드는 한개의 부모 노드만을 가짐

부모-자식

그래프 (Graph)
부모-자식의 개념이 없음
트리 (Tree)
부모- 자식 관계가 존재하며, top-bottom 또는 bottom-top으로 이루어짐

모델

그래프 (Graph)
네트워크 모델
트리 (Tree)
계층 모델

순회

그래프 (Graph)
DFS¹, BFS²
트리 (Tree)
DFS¹와 BFS²안의 Pre-, In-, Post-order

간선의 수

그래프 (Graph)
그래프에 따라 간선의 수가 다르며, 간선이 없을 수도 있음
트리 (Tree)
노드가 $n$인 트리는 항상 $n-1$의 간선을 가짐

경로

그래프 (Graph)
-
트리 (Tree)
임의의 두 노드 간의 경로는 유일

예시 및 종류

그래프 (Graph)
지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목 등…
트리 (Tree)
이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대 힙, 최소 힙) 등…

오일러 경로 (`Eulerian tour`)

그래프에 존재하는 모든 간선(edge)을 한 번만 통과하면서 처음 정점(vertex)으로 되돌아오는 경로를 말하며, 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다.

참고 사이트

heejeong Kwon - [자료 구조] 그래프(Graph)란
cocoacolar.log - [Algorithm] 자료 구조 그래프(Graph)

Depth First Search, 깊이 우선 탐색 ↩︎ ↩︎² ↩︎³
Breadth First Search, 너비 우선 탐색 ↩︎ ↩︎² ↩︎³
트리 (Tree) : 사이클을 가지지 않는 연결 그래프 ↩︎ ↩︎²
단순 경로(Simple Path) : 경로 중에서 반복되는 정점이 없는 경우 ↩︎
Array List : 동적 가변 크기 배열 ↩︎
Linked List : 연결 리스트 ↩︎
Directed Acyclic Graph, 방향성이 있는 비순환 그래프 ↩︎

Computer Science, Data Structure