[자료구조] Graph_1. 그래프의 개념과 특징

그래프(graph)자료구조의 개념부터 해서 이와 관련된 disjoint-set 등의 다양한 알고리즘까지 쭉 정리해보려 한다.

하나의 게시글에 정리하려고 하니 양이 너무 많을 듯해서, 시리즈로 쪼개서 정리해보려 한다.

우선은 Disjoint set에 대해서 쭉 정리하고 공부하려 한다.

1. 그래프의 개념과 특징(현재글)
2. Graph_disjoint set
3. Union Find 최적화

---

그래프(Graph)의 개념

노드와 그 노드를 연결하는 간선을 하나로 모아놓은 자료구조이다.  즉, 연결되어 있는 객체간의 관계를 표현하는 자료구조이다. 

그래프는  non-linear / 네트워크 모델이다. 

그래프는 트리와 가장 많이 비교가 되는데 그 차이를 아래 표를 통해 살펴볼 수 있다.

 

그래프와 관련된 용어

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

 

Type of "grahps"

undirected graphs(무방향 그래프)

아래 그림처럼 두 노드 간에 특정한 방향(direction)이 없는 양방향(two-way relationship) 그래프이다. 

leet code 출처

Directed graphs(방향 그래프)

두 노드 간의 관계성에 방향성이 있는 그래프이다.

 

Weighted graphs(가중치 그래프)

두 노드를 연결한 간선 간에 비중(weight)가 있는 graph이다. 보통 시간, 거리, 크기 등을 표현가능 하다. 

 

기타 종류

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

• 연결 그래프(Connected Graph)
  무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
  Ex) 트리(Tree): 사이클을 가지지 않는 연결 그래프
• 비연결 그래프(Disconnected Graph)
  무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우

사이클 VS 비순환 그래프

• 사이클(Cycle)
  단순 경로의 시작 정점과 종료 정점이 동일한 경우
  단순 경로(Simple Path): 경로 중에서 반복되는 정점이 없는 경우
• 비순환 그래프(Acyclic Graph)
  사이클이 없는 그래프

완전 그래프

• 완전 그래프(Complete Graph)
  그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
• 무방향 완전 그래프
  정점 수: n이면 간선의 수: n * (n-1) / 2
  
  

그래프의 구현방법

1. 인접 리스트(Adjacency List)

인접 리스트(Adjacency List)로 그래프를 표현하는 것이 가장 일반적인 방법 이다.
모든 정점(혹은 노드)을 인접 리스트에 저장한다. 즉, 각각의 정점에 인접한 정점들을 리스트로 표시한 것이다.
배열(혹은 해시테이블)과 배열의 각 인덱스마다 존재하는 또 다른 리스트(배열, 동적 가변 크기 배열(ArrayList), 연결리스트(LinkedList) 등)를 이용해서 인접 리스트를 표현할 수 있다.

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 클래스 불필요
그래프에선 특정 노드에서 다른 모든 노드로 접근이 가능하지는 않음 -> Graph 클래스 필요

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. 너비 우선 탐색) 또한 인접 행렬에서도 사용이 가능하다.
하지만 인접 행렬은 조금 효율성이 떨어진다. 인접 리스트는 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있지만 인접 행렬에서는 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다.

 

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

• 인접 리스트 : 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우
  
  • 인접리스트의 장점
    • 정점들의 연결 정보를 탐색할 때 O(n) 시간이면 가능하다.
    • 필요한 만큼의 공간만 사용하기 때문에 공간의 낭비가 적다.
  • 인접리스트의 단점
    • 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래걸린다. (O(E) 시간 소요. E는 간선의 개수)
    • 구현이 비교적 어렵다.
• 인접 행렬 : 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph) 의 경우
  
  • 인접행렬의 장점
    • 2차원 배열 안에 모든 정점들의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결 정보를 조회할 때 O(1) 의 시간복잡도면 가능하다.
    • 인접리스트에 비해 구현이 쉽다.
  • 인접행렬의 단점
    • 모든 정점에 대해 간선 정보를 대입해야 하므로 $O(n^2)$ 의 시간복잡도가 소요된다.
    • 무조건 2차원 배열이 필요하기 때문에 필요 이상의 공간이 낭비된다.
      
      

 

Reference

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

https://hongcoding.tistory.com/78

https://libertegrace.tistory.com/entry/3-ES6-Practice?category=869766