자료구조: 그래프(Graph)

그래프는 정점 (node 또는 vertice)와 간선 (edge)로 이루어진 자료구조이다. 여기서 노드에는 데이터가 저장되고 엣지는 두 노드 사이의 관계를 나타낸다.

 

위 그래프에서 노드는 {1, 2, 3, 4, 5} 이고 엣지는 {12, 13, 23, 25, 34, 45}이다.

 

그래프의 종류에 대해서 알아보자.

• Directed Graph (방향 그래프): 두 노드를 연결하는 엣지의 방향이 존재하는 그래프. 왼쪽 그래프에서 엣지 1->2는 존재하지만 2->1 은 존재하지 않는다. edge(12) ≠ edge(21)
• Undirected Graph (무방향 그래프): 두 노드를 연결하는 엣지의 방향이 없이 양방향으로 연결되는 그래프. 오른쪽 그래프에서 엣지 1->2와 2->1이 같다. edge(12) = edge(21)

왼쪽이 Directed Graph, 오른쪽이 Undirected Graph

• Cyclic Graph: 한 노드에서 출발하여 자기 자신으로 다시 돌아오는 경로가 있는 그래프.
• Acyclic Graph: 한 노드에서 출발하여 자기 자신으로 다시 돌아오는 경로가 없는 그래프.

왼쪽이 Cyclic, 오른쪽이 Acyclic

그래프를 표현하는 방식에는 두 가지가 있다.

• Adjacency Matrix (인접 행렬): 2차원 배열을 사용해서 그래프를 표현한다. 2차원 배열이기 때문에 노드의 수에 제곱만큼의 공간을 차치하지만 구현이 간단하다. 예를 들어, 아래의 그래프처럼 A와 B 사이에 엣지가 있다면 배열에서 [A][B]의 값이 1이 되고 [B][A]의 값도 1이 된다. (Undirected Graph 이기 때문에)

• Adjacency List (인접 리스트): 연결 리스트를 사용해서 그래프를 표현한다. 공간은 노드 수와 엣지의 수를 합한 만큼만 차지하지만 구현이 복잡하다. 예를 들어, 아래의 그래프에서 A 노드와 엣지로 연결된 인접한 노드들이 리스트 형태로 표현된다.

따라서 노드의 수가 적으면 Adjacency Matrix, 많다면 Adjacency List로 구현하는 게 좋다.