기본 그래프 알고리즘

그래프 알고리즘

누군과의 관계를 표현할 때, 우리는 두 노드를 그리고 선을 긋는다. 트리 알고리즘이 위계를 나타낸다면, 그래프는 두 노드간의 관계를 나타낸다. 그래프는 vertices(정점)와 그 사이를 잇는 edges(간선)로 이루어진 자료구조이다.

만약, 주어진 그래프 $G = (V,E)$가 있다면,

• V : 정점(vertices)의 개수
• E : 간선(edges)들의 개수

• 알고리즘 수행시간 : $

  V

  ,

  E

  $ 의 두 매개변수의 관점에서 입력의 크기를 표현한다.

그래프를 표현하는 방법

그래프는 표현하는 방법에는 두 가지가 있다. 인접리스트와 인접행렬이다.
그리고 한 그래프를 탐색한다는 것(Searching a graph)은 그래프의 모든 정점을 방문하기 위해 해당 그래프의 간선을 조직적으로 따라가는 것을 의미한다. 그래프 검색 알고리즘은 그래프의 구조에 대해 많이 알아낼 수 있다. 다음은 그래프에서 가질 수 있는 속성이고 그 속성에따라 그래프가 분류된다.

• 방향성
  1. 무방향 그래프 : 간선의 방향이 정해진 그래프이다.
  2. 방향 그래프
• 가중치
  1. 가중치 그래프 : 간선의 가중치값이 있는 그래프이다.
  2. 가중치가 없는 그래프

인접리스트

• 정의 : 정점들의 집합 $

  V

  $에 속한 $u$ 정점에 대해 인접리스트 $Adj[i]$는 $(u,v) \in E$가 존재하는 모든 정점을 가진다.

• 낮은 밀도의 그래프를 표현하기에 좋다. ($

  E

  $가 $

  V

  ^2$ 보다 작을 때 즉, 간선의 개수가 노드의 개수보다 비교적 적을 때)

• 인접리스트 길이의 총 합 : $

  E

  $

• 필요한 메모리양 : $\theta(V+E)$ 정점의 개수가 V개이고, 모든 간선의 개수가 E개이기때문에 두 값을 더한 공간에 인접리스트를 할당한다면 그래프를 표현할 수 있다.
• 그래프의 종류에 따른 인접리스트 표현

  1. 무방향 그래프 : 이때 인접리스트의 길이는 $2

     E

     $이다.

  2. 가중치 그래프 : $w:E -> \mathbf{R}$의 값이 인접리스트에 저장된다면 가중치 그래프도 표현이 가능하다.
• 단점 : 주어진 간선 $(u,v)$가 그래프에 있는지 확인하기 위해서는 인접리스트에서 $v$를 검색하는 것 보다 빠른 방법이 없다. 이 속도를 개선한 인접리스트 응용이 있긴 하다.

인접행렬

• 정의 : $|V| \times |V|$ 크기의 행렬 $\mathbf{A} = (a_{ij})$ 로 표현된다. $a_{ij} = \begin{cases} 1 & if (i,j) \in E
  0 otherwise \end{cases} $

• 높은 밀도의 그래프를 표현하기에 좋다. ($

  E

  $가 $

  V

  ^2$와 비슷할 때. 즉, 간선의 개수가 많을 때)

• 필요한 메모리양 : $\theta (V^2)$ $V \times V$ 의 크기를 가진 행렬을 담기 때문이다. 무방향 그래프일 경우, 대각 행렬이며 그 위 데이터만 저장한다면 메모리양을 절반으로 줄일 수 있는 방법도 있다.
• 그래프의 종류에 따른 인접행렬의 표현
  1. 무방향 그래프 : 이때 인접행렬로 표현한다면 행렬 $\mathbf{A}$은 대각행렬이 되며, $\mathbf{A} = \mathbf{A}^T$ 이 행렬은 그를 전치한것과 같다.
  2. 가중치 그래프 : 행렬 요소로 가중치값을 저장하여 표현할 수 있다.

인접리스트 vs 인접행렬

메모리 저장공간 측면에서 인접리스트가 효율적일 수 있으나, 인접행렬이 표현이 단순하여 더 많이 쓰인다. 그리고 가중치가 없는 그래프일 경우, 인접행렬의 요소로 한 비트만 저장되면 된다.