[자료구조] Graph

그래프 정의 

다양한 그래프들

G = (V, E)
V : 공집합이 아닌 유한한 정점의 집합
E : 유한한 edge들의 집합.

 

그래프 종류

방향성에 따른 분류

• Undirected Graph
  방향성이 없는 그래프 (u, v) = (v, u)
• Directed Graph
  방향성이 있는 그래프 < u, v > != < v, u>

위 사진의 a, b가 undirected이고 c가 directed이다. 

 

순환성에 따른 분류

• Cyclic Graph
  시작과 끝이 동일한 path가 있는 그래프
• Acyclic Graph
  순환할 수 없는 그래프 (tree가 대표적인 acyclic graph이다.)

가중치에 따른 분류

• Unweighted Graph
  edge에 가중치가 없는 경우 
• Weighted Graph
  edge에 가중치가 있는 경우 / 인접 행렬에서는 a[i][j]에 인접리스트는 노드 구조에 가중치 정보를 저장한다. 

그 외 정의

• Complete Graph
  n개의 정점이 있을 때 n(n-1)/2 개의 edge를 가진 undirected graph 
  ( = 서로 다른 두 개의 꼭짓점이 하나의 변으로 연결된 그래프

왼쪽은 complete graph이고 오른쪽은 아니다.

• MultiGraph
  두 정점 사이에 path가 여러개 있는 상황. 보통 알고리즘 문제를 해결할 때에는 path가 하나라고 가정하지만, 실제 세계는 여러 개인 경우가 더 많다. 

• adjacent
  undirected graph의 정점 u, v에 대하여 간선 (u, v)가 있다면 정점 u는 v에 인접했다고 한다. 
  u is adjacent to v == v is adjacent from u
• incident
  undirected graph의 정점 u, v에 대하여 간선 (u, v)가 있으면 간선 (u, v)는 간선 (u, v)는 정점 u와 v에 부속 (incident)한다고 한다. 

 

• Subgraph
  말 그대로 한 그래프 안에 포함된 그래프 구조들을 말한다. 

 

• connected component : 연결된 정점 집합
• Strongly connected component : '강하게' 연결된 정점 집합
   : V(G)에 있는 모든 정점 간 u -> v와 v -> u path가 모두 존재할 때 강하게 연결되었다고 한다.
  
  

 

 

그래프 표현

1. Adjacency matrix

vertex에 대해 2차원 배열을 생성하고 각 vertex에 대해 인접한 vertex를 1, 아닌 것을 0으로 할당한다. 방향성이 없을 때는 대각선을 기준으로 대칭의 형태를 보인다. 

인접 행렬의 장점

•  i과 j 사이의 edge를 찾을 때 탐색시간이 O(1)이다. (A[i][j] 로 하면 바로 나오니까) 
• 행렬 곱 연산을 진행할 때 유리하다.

power of matrix

인접 행렬의 단점

• 많은 메모리 공간의 소요 ( vertex는 많은데 edge가 적은 경우 희소행렬이 되어 공간 낭비)
  -> undirected의 경우 upper 공간만 제작해 만드는 등 메모리 공간을 줄이는 노력을 할 수 있다. 
• 그래프에 존재하는 edge의 개수를 셀 때 많은 시간이 소요된다. -> n^2 - n 번 탐색 = O(n)

 

2. Adjacency List

vertex에 adjecent한 vertex를 lined list 형태로 표현한다. 그래프가 sparse할 경우 인접 행렬 방식보다 훨씬 효육적으로 사용할 수 있다. 

+) Inverse Adjacency List (역 인접 리스트)
정점에 인접한 정점에 대한 표현을 한다. ( 인접 리스트와 반대 )

그냥 adjacency list는 자기가 갈 수 있는 곳을 기록해두는데 inverse adjecency는 자기에게 올 수 있는 노드를 기록한다고 생각하면 쉽다. 

 

3. Sequential List

인접리스트를 1D로 나타낼 수 있다. n개의 head node와 2e개의 list node들이 필요하다. (배열의 총 크기 : n + 2 * e + 1)

위 그림에서 0 ~3 번째 index의 값은 vertex에 연결된 edge의 정보가 있는 곳을 나타낸다. 
ex ) node[0] = 5 -> node[5]부터 vertex 0번에 대한 정보를 가지고 있음

4번은 배열의 끝의 값을 나타낸다. 이 표현으로 node와 node 정보 영역을 구분할 수 있다.  

 

 

 

그래프 응용

1. Euler's walk
2. Road Networks(subway networks)
3. Communication networks
4. Computer systems
5. Foreign exchange, multinational tax planning
6. Social graph