그래프

용어

그래프 자료구조는 Vertex(정점, node) 와 Edge(간선, line) 으로 이루어진다. 그래프는 방향성의 유무와 가선 가중치의 유무에 따라 종류가 나뉠 수 있다.

 

Path

그래프의 Path 는 간선들로 이어진 연속된 정점들의 집합이다. 이 때, 반복된 Vertex(정점)이 없는 path를 Simple Path(단순 경로) 라고 부른다.

 

Connect(연결)

무방향 그래프가 Connect 되어 있다는 것은 모든 정점들에 대한 하나의 Path 가 있다는 것이다.

무방향 그래프 C가 무방향 그래프 G의 Connect Component 가 되려면 C는 G의 하위 그래프이고 C는 connect되어야 하며, G의 connect 되지 않은 서브 그래프가 C를 서브 그래프로 볼 수 있어야 한다.

SCC(Strongly Connected Component)는 방향 그래프에서 한 정점에서 출발하여 어떤 정점으로도 갈 수 있는 정점들의 최대 집합이다.  

Adjacent(인접)

방향 그래프에서 u-> v 엣지에 대하여 v는 u와 adjacent(인접) 해 있다고 표현한다. (그 반대는 성립하지 않는다.)

방향 그래프에서 정점 v에 대하여 in-degree/out-degree 을 구별할 수 있는데 in-degree는 정점 V로 들어오는 엣지의 개수이고 out-degree는 정점 v에서 나가는 엣지의 개수이다.

 

Cycle

Cycle(사이클)은 같은 정점에서 시작하여 같은 정점으로 끝나는 path를 의미한다.

acyclic graph는 사이클을 포함하지 않는 그래프이다.

무방향 그래프에서 두 정점 사이의 엣지가 하나 있는 상태는 사실 Cycle이지만 고려하지 않는다.

방향 그래프에서 Cycle 이 없는 그래프를 DAG(Directed Acyclic Graph)라고 부른다.

 

 

특별한 그래프

• Tree: 무방향 이면서 Edge 의 수가 (Vertex의 개수 - 1) 인 최소 연결 그래프이다. 트리라고 해서 모두 root 를 갖춘 것은 아니다. 
• RootedTree: 루트 노드를 갖는 형태를 취한 트리이다. 나머지 노드들은 루트 노드의 아래에 위치하여 계층적인 모습을 갖는다.
• Binary Tree: 노드가 최대 2개의 자식 노드를 갖는 Rooted Tree 이다.
• Full Binary Tree: 모든 노드가 2개의 자식 노드를 갖춘 Binary Tree 이다.
• Complete Binary Tree: 마지막 레벨을 제외하고 모든 레벨에 노드가 존재하고 마지막 레벨은 왼쪽부터 노드가 채워진 Binary Tree 이다. Binary Heap 이 갖는 트리의 특성이기도 하다.
• Complete Graph: 엣지의 수가 E = V*(V-1)/2 이면서 모든 정점 쌍 사이에 엣지가 존재하는 그래프이다.
• Bipartite Graph(이분 그래프):
  무방향 그래프에 대해서 정점을 서로 겹치지 않는(간선이 존재하지 않는, 연결되지 않는) 두 정점 집합으로 나눌 수 있으며 모든 간선은 서로 다른 집합의 정점으로 구성되어야 한다. 즉, 같은 집합 내에 간선이 존재하지 않아야 한다.
  => 쉽게 설명하면 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프이다.
  만약 사이클이 존재한다면 간선의 숫자는 짝수여야 한다. 
  완전 이분 그래프는 한 그룹의 정점이 다른 그룹의 모든 정점들에 대하여 간선이 있는 이분 그래프를 가리킨다. 따라서, 각 그룹의 정점의 개수가 U 와 W 라면 총 간선의 수는 U * W 이다.
  자연스럽게, Tree는 이분 그래프이다. 
• DAG(Directed Acyclic Graph): 사이클이 없는 방향 그래프

 

그래프를 표현하는 방법

1. 인접 행렬

2차원 배열 graph[i][i] 로 표현하고 i, j 는 Vertex 를, graph[i][j] 는 정점 i 와 j 의 간선을 나타낸다.

가중치 그래프의 경우 graph[i][j] 값은 가중치를 나타내며 무가중치 그래프의 경우 graph[i][j] 는 간선이 있으면 1, 없으면 0을 나타낸다.(가중치 그래프의 경우 가중치가 0인 간선이 존재한다면 두 정점 사이의 간선의 없음을 -1 처럼 다른 값으로 표현해야 한다.)

 

공간복잡도는 O(V^2) 

두 정점 사이의 간선 조회가 O(1) 시간복잡도 가지므로 간선 조회가 빈번히 일어나거나 밀집 그래프를 다룰 때 사용하면 좋다.

 

2. 인접 리스트

리스트 배열 vector<vector<pair<int, int>> graph 표현하고 행에 위치한 값은 시작 정점 인덱스를 열에 위치한 pair<int, int> 값은 도착 정점과 가중치 값(가중치 그래프의 경우)을 나타낸다. vector 을 사용하는 이유는 벡터는 가변적인 자료구조이기 때문이다.

 

공간복잡도는 O(V+E) 행은 정점의 수만큼있지만 열은 가선 수 만큼 있기 때문에 이와 같은 공간복잡도를 갖는다.

각 정점에 대한 인접한 정점 목록을 바로 확인할 수 있으므로, 그래프 탐색 알고리즘에서 효율적으로 이웃을 순회할 수 있다.

 

3. 간선 리스트

두 정점 과 가중치 값을 지닌 객체 리스트로 표현된다. 보통 가중치 값으로 정렬하여 사용되는데 MST 문제의 크루스칼 알고리즘에서 볼 수 있다.

 

공간복잡도는 O(E), 간선 수 만큼 공간을 차지한다.

간선 중심의 처리가 많은 알고리즘에서 사용하면 좋다.

 

단순한 어플리케이션

Counting V

인접 행렬 혹은 인접 리스트의 경우 정점의 수를 카운팅 하는 행위에 대한 시간 복잡도는 O(1) 혹은 O(V) 이다.

간선 리스트의 경우 모든 간선을 순회화면서 집합(Set) 에 정점을 저장한 후 순회가 끝났으면 집합의 크기를 계산하는 식으로 알고리즘을 짤 수 있고 시간복잡도는 간선 순회에 O(E), 집합의 크기 계산은 O(V) 혹은 O(1) 이 걸린다.

Counting E

간선 리스트의 경우 O(E) 혹은 O(1) 이 걸린다.

인접 리스트의 경우 모든 정점의 리스트를 더하고 나누기 계산할 수 있다.(무방향 그래프의 경우 계산결과에 나누기 2를 해야 한다.) 시간 복잡도는 O(V+E) 이다. 구현에 따라서 O(V) 시간 복잡도를 가질 수 있다.(각 정점의 리스트 크기를 갖고 있는 경우)

인접 행렬의 경우 모든 행렬의 i,j 인덱스를 순회하면서 간선 존재 여부를 확인하고 카운팅한다. (무방향 그래프의 경우 계산결과에 나누기 2를 해야 한다.) 시간 복잡도는 O(V^2) 이다.

정점의 인접한 이웃 찾기

인접 행렬의 경우 한 정점의 모든 열을 순회하면서 간선의 존재 여부를 확인해야 하므로 시간 복잡도는 O(V) 이다.

인접 리스트의 경우 해당 정점의 인접한 이웃 수 만큼 순회하면 되므로 한 정점의 이웃이 k라고 할 때 시간 복잡도는 O(k) 이다.

간선 리스트의 경우 모든 간선을 순회하면서 찾아야 하므로 시간 복잡도는 O(E) 이다.

간선(u,v)의 존재 유무 확인

인접 행렬의 경우 인덱스를 이용하여 바로 확인할 수 있어 시간 복잡도는 O(1) 이다.

인접 리스트의 경우 시작 정점의 이웃을 탐색해야 하므로 이웃의 수를 k라고 했을 때 시간 복잡도는 O(k) 이다.

간선 리스트의 경우 모든 간선을 탐색해야 하므로 시간 복잡도는 O(E) 이다.