Graph

Graph 란?

자료구조의 그래프는 마치 거미줄처럼 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습을 갖는다.

Graph의 구조

• 하나의 점을 그래프에서 정점(vertex) 이라고 하고, 하나의 선은 간선 (edge)라고 한다.

Graph 의 표현방식

인접 행렬

• 두 정점을 바로 이어주는 간선이 있다면 두 정점은 인접하다고 한다.
• 인접 행렬은 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다.
  • 이어져 있다면 1 (true)
  • 이어져 있지 않다면 0 (false)로 표시한다.
• 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장한다.

인접 행렬은 언제 사용할까?

• 두 정점사이에 관계가 있는지 , 없는지 확인하기에 용이하다.

  • ex ) A에서 B로 진출하는 간선이 있는지 파악하기 위해서는 0 번째 줄의 1 번째 열에 어떤 값이 저장되어 있는지 바로 확인 할 수 있다.

• 가장 빠른 경로(shortest path)를 찾고자 할 때 사용

인접 리스트

• 인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한 것이다.

• 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

위는 인접리스트로 표현한 것을 나타낸 것이다. 이때 우리는 한가지 의문을 갖을 수 있다.

• 이 그림에서 B는 A와 C로 이어지는 간선이 2개가 있는데, 왜 A가 C보다 먼저일까? 이 순서는 중요한가?

  • 보통은 중요하지 않다. 그래프, 트리, 스택, 큐 등 모든 자료구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제 할 수 있다.
    그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선 순위를 고려해 구현할 수 있는데 이때, 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있다.
    • 우선 순위가 없다면 연결된 정점들을 단순하게 나열한 리스트가 된다.

• 우선 순위를 다뤄야 한다면 더 적합한 자료구조 (queue, heap)를 사용하는 것이 합리적이다.

• 인접 리스트는 언제 사용할까?

  • 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.