그래프

그래프는 정점(Vertex)간선(Edge) 으로 이루어진 자료의 집합으로 어떤 상태나 객체 사이의 관계를 나타낼때 사용합니다. 정점은 어떤 상태나 객체를 나타내고, 간선은 정점간의 연결성을 나타내며 경우에 따라 간선은 가중치(혹은 비용)라는 값을 가지기도 합니다.

더 설명하기에 앞서 글에서 사용할 표현을 정리하겠습니다.

  • E(u, v) 정점 u에서 나가 v에 도달하는 간선
  • W(u, v) 간선 E(u, v)의 가중치
  • u -> v 정점 u에서 v로 이동을 의미
  • V 그래프의 정점 수
  • E 그래프의 간선 수
  • 정점 u, v가 인접(Adjacent)하다 정점 u, v가 간선으로 연결되어 있음을 의미
  • 희소 그래프(Sparse Graph) 간선의 수가 적은 그래프
  • 밀집 그래프(Dense Graph) 간선의 수가 V * V에 가까운 그래프

그래프의 종류에는 유향 그래프(Directed Graph)와 무향 그래프(Undirected Graph)가 있습니다. 유향 그래프와 무향 그래프는 간선에 방향성이 있는지에 따라 달라집니다. 예를 들어 정점 u와 v가 있고 두 정점이 간선으로 연결되어 있을때 무향 그래프에서는 u->v가 가능하다면 v->u도 가능해야하며 반대로 u->v가 불가능하다면 v->u 역시 불가능 해야합니다. 결과적으로 무향 그래프에서 E(u, v) 혹은 E(v, u)가 있으면 그 반대 역시 암묵적으로 존재하는 것입니다. 하지만, 유향 그래프에서는 E(u, v)가 존재하여 u->v가 가능한다고 해도 E(v, u)가 존재하지 않다면 v->u가 불가능합니다.

정점과 간선 외에 그래프에서 사용하는 또 다른 개념으로 차수(Degree) 가 있습니다. 차수는 유향 그래프에서만 사용하는 개념입니다. 차수는 입력차수(In-degree)와 출력차수(Out-degree)가 있는데, 정점 v의 입력 차수는 정점 v로 들어오는 간선의 수를 말하며 출력 차수는 정점 v에서 시작되어 다른 정점으로 가는 간선의 수를 의미합니다.

그래프의 표현

그래프를 프로그래밍적으로 표현하는 방법은 크게 인접 행렬(Adjacent Matrix)과 인접 리스트(Adjacent List)가 있습니다.

인접 행렬

만약 위와 같은 그래프를 인접 행렬로 표현한다고 한다면 V*2 크기의 2차원 배열이 필요하며 배열의 내용은 아래와 같이 채워지게 될것입니다.

  1 2 3 4
1 0 1 1 0
2 1 0 0 1
3 1 0 0 0
4 0 1 0 0

인접 행렬의 O(V * V) 공간에 그래프의 정보를 저장하여 표현합니다. 인접 행렬로 표현하면 두 정점의 연결 상태를 O(1)에 바로 확인이 가능하다는 것이 큰 장점이 됩니다. 단점은 그래프의 모든 간선을 확인하는데 O(V * V) 시간이 걸린다는 것입니다. 왜냐하면 모든 간선 정보를 확인하며 연결되어 있는지 되어있지 않는지 검사해야하기 때문입니다.

인접 리스트

배열의 모든 상태를 공간에 저장하는 인접 행렬과는 다르게 인접 리스트는 존재하는 간선의 정보만 가지고 있어 인접 행렬보다 훨씬 적은 공간에 필요한 정보를 저장할 수 있습니다. 또한 그래프의 모든 간선을 확인하는데 O(E) 밖에 걸리지 않기 때문에 대부분의 경우에 이 방법을 사용하는 것이 시간적으로나 공간적으로나 효율적입니다.

List[1] = { 2, 3 }
List[2] = { 1, 4 }
List[3] = { 1 }
List[4] = { 2 }