[자료구조] 그래프(Graph)

 

그래프라는 자료구조는 정점(Edge)과 간선(Vertex)으로 이루어진 자료 구조를 의미한다. 

트리(Tree)또한 그래프의 일종이며 차이점은 그래프는 '사이클'을 생성한다는 점이다. 

 

그래프 구현 방식

인접 리스트(Adjacency List)

인접 리스트 방식은 각 정점마다 하나의 연결 리스트를 통해 연결된 모든 정점을 저장하는 방식이다.

예를 들어, 이런식이다.

• 인접 리스트:
  0: 1 2 
  1: 0 2 
  2: 0 1 3 
  3: 2 4 
  4: 3 

해당 예시에는 0, 1, 2, 3, 4이라는 정점이 존재하며, 각 정점마다 하나의 연결 리스트를 통해 연결된 모든 정점을 저장하고 있다.

 

인접 행렬(Adjacency Matrix)

반면, 인접 행렬 방식은 2차원 배열(matrix)의 값에 해당 정점 사이의 간선 여부를 저장하는 방식이다.

예를 들어, 정점의 개수를 V라고 할 때, V x V 크기의 2차원 배열을 사용하여 인접 행렬을 나타낼수 있다.

만약, 정점 a와 b가 연결되어 있다면, 행렬의 a행과 b행의 위치에는 간선을 나타내는 표시(예를 들어, 1이나 true)가 들어가게 된다. 반대로 그렇지 않은 경우에는 간선이 없음을 나타내는 표시(예를 들어, 0이나 false)가 들어가게 되는 것이다. 

예시는 다음과 같다.

• 인접 행렬:
  0 1 1 0 0 
  1 0 1 0 0 
  1 1 0 1 0 
  0 0 1 0 1 
  0 0 0 1 0

2차원 배열이기에 이는 0부터 4까지의 다섯 개의 정점를 가진 그래프를 나타내는 예시이며, [0][1], [1][0]에 각각 1이 있다는 것은 1과 0 사이에 양방향으로 간선이 존재한다는 의미이다.

 

인접 리스트 방식의 성능

• 두 정점이 서로 연결되어 있는지 확인할 때

연결 리스트를 탐색해야 하므로 시간 복잡도는 O(V)

 

• 한 정점에 연결된 모든 정점을 찾는 경우

해당 정점의 연결 리스트에 있는 모든 정점을 탐색하므로 시간 복잡도는 O(V)

공간 복잡도는 O(V + E) (V: 정점 수, E: 연결리스트(간선)의 갯수)

 

인접 행렬 방식의 성능

•  두 정점이 서로 연결되어 있는지 확인할 때

해당 위치의 값을 조회하기만 하면 되므로 O(1)

 

• 한 정점에 연결된 모든 정점을 찾는 경우

해당 정점과 모든 정점의 연결 여부를 조회해야 하므로 시간 복잡도는 O(V)

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

• •  

그래프 순회방식

• DFS (Depth First Search)
  • 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다
  • 스택 자료구조, 재귀 함수 이용
  • 인접 행렬로 구현시 O(n^2)
  • 인접 리스트로 구현시 O(n+m)
• BFS (Breadh First Search)
  • 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다
  • 큐 자료구조 이용
  • 인접 행렬로 구현시 O(n^2)
  • 인접 리스트로 구현시 O(n+m)