저자 Dasgupta의 Algorithms을 해석하면서 정리한 글입니다.

Chapter 3. Decompositions of graphs

3.1 Why graphs?

광범위한 문제는 graph의 간결한 그림으로 명확하고 정확하게 표현할 수 있습니다.
예를 들어, Graph Coloring은 이웃 나라 또는 지형에 따라 다른 색을 칠해야 하고, 학교에서 시험 시간표가 겹칠 때 활용할 수 있습니다.
만일 어떤 학생이 동시에 진행되는 두 시험을 모두 치르려 한다면, 두 시험이 동시에 시간표로 만들어질 수는 없습니다.
그래프에선 이 문제를 표현하기 위해서 각 시험에 대해 한 정점(Node)을 사용하고, 만일 충돌이 있을 경우엔 두 정점 사이에 간선(Edge)를 두는 것으로 해결할 수 있습니다. 각 시험 시간마다 자신의 색상을 갖는 것으로 시간 배정을 하는 것은 그래프를 색칠하는 것과 같게 볼 수 있습니다. 이 외에도 지하철의 노선도 등 실생활에서도 여기저기에 그래프를 활용할 수 있습니다.

Definition of Graph

그래프는 단순하게 정점(Node)과 이 정점들을 연결하는 간선(Edge)을 모아놓은 일종의 자료구조 입니다. 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있게 도와주는 도구입니다.

3.1.1 How is a graph represented?

무방향 그래프(Undirected Graph)

무방향 그래프(Undirected Graph)는 보통 G = (V, E)로 표현됩니다. 여기서 V는 정점(Node)을 이야기하고, E는 정점들을 연결하는 간선(EdgE)를 뜻합니다.

$V$ = {$1,2,3,4,5,6,7,8$}
$E$ = {$(1,2), (1,3), (2,3), (2,4), (2,5), (3,5), (3,7), (3,8), (4,5), (5,6), (7,8)$}

예를 들어, 위와 같이 $V$와 $E$가 정의된다면, 그래프는 다음과 같습니다.

무방향 그래프의 특징은 이 간선들이 방향이 없다는 것입니다. 즉, 정점들 사이에 정해진 방향은 없습니다.

인접 행렬(adjacency matrix)

인접 행렬(adjacency matrix)은 $n * n$ 행렬로, 각각은 i번째 행과 j번째 열이 0과 1로 나타냄으로써 그 의미가 그래프와 동일해질 수 있습니다.

만약 i번째 정점과 j번째 정점이 간선으로 연결되어 있다면, 해당하는 곳에는 1이 적힙니다. 반대로 간선이 존재하지 않는다면 0이 적힙니다.
무방향 그래프이기 때문에 인접 행렬은 대각선을 기준으로 대칭입니다.

예를 들어 다음의 왼쪽의 그래프를 통해서, 이 그래프를 행렬로 표현할 수 있다.

인접 행렬은 정점 i와 j가 연결되어 있는지 확인하고 싶으면, 해당하는 칸의 값이 0인지 1인지만 확인하면 되기 때문에 시간 복잡도는 $O(1)$입니다.

하지만, 특정 정점 i에 연결된 모든 정점들을 방문하고 싶을 때는 해당 i행의 모든 열을 확인해야 하기 때문에 $O(n)$의 시간 복잡도가 걸리기도 합니다. 즉, 모든 정점을 확인하기 위해서는 n의 제곱만큼의 시간 복잡도가 필요하게 됩니다.

인접 리스트(adjacency List)

인접 행렬이 행렬로 그래프를 표현한 것이라면, 인접 리스트는 리스트로 그래프를 표현한 것입니다. 그 중에서도 Linked List로 표현이 되는데, Linked List는 무방향 그래프를 나타내야 하기 때문에 서로 반대 방향을 모두 연결시켜야 합니다.
그래서 다음 그래프와 리스트를 살펴보면 1이 2와 연결되어 있는 것을 2에서 1로 연결되도록 중복해서 적은 것을 볼 수 있습니다.

인접 리스트는 인접 행렬과 달리, 실제로 연결된 정점들에 대한 정보만을 갖고 있기 때문에, 모든 방향선의 원소 개수의 합이 간선의 개수와 같습니다.

예를 들어, 정점 2와 연결된 모든 정점을 방문하고 싶다면, 인접 행렬의 경우 총 7번을 확인해야 하지만, 인접 리스트의 경우 실제 연결된 정점만 확인하면 되기에 4번만 확인하면 됩니다.
모든 정점을 확인한다고 했을 때, 인접 리스트는 각 정점마다 연결된 정점만 확인하는 것이 가능하기에, 전체 간선의 개수와 정점만 확인해주면 됩니다. 따라서 정점의 개수 + 간선의 개수만큼의 시간 복잡도만 필요하게 됩니다.

Reference

1. Algorithms - Dasgupta