목차

1. 그래프란?

그래프는 정점과 간선으로 이루어진 자료구조이다. 그래프는 다음과 같은 특징을 가진다.

2. 그래프의 활용

그래프는 주로 탐색을 위해 사용된다. 여기에서 탐색이란 그래프의 정점(vertex)을 방문하기 위해 간선(edge)을 따라 이동하는 것을 의미한다. 탐색을 통해 그래프의 구조를 파악하거나 특정 정점을 찾는 등의 작업을 수행할 수 있다. 대표적인 예시로는 미로 찾기, 최단 경로 찾기, 네트워크 경로 찾기 등이 있다.

그래프 탐색 알고리즘에는 다음과 같은 것들이 있다.

3. 그래프 표현 방법

대표적으로 그래프는 대표적으로 다음의 두 가지 방법으로 표현할 수 있다

3.1 인접 행렬(Adjacency Matrix)

인접 행렬은 2차원 배열로 그래프를 표현하는 방법이다. 인접 행렬은 다음과 같은 특징을 가진다.

matrix = [[1, 0, 0, 1, 0],
          [0, 1, 1, 0, 0],
          [0, 1, 1, 1, 1],
          [1, 0, 1, 1, 0],
          [0, 0, 1, 0, 1]]

인접 행렬은 다음과 같은 장단점을 가진다.

인접 행렬은 정점의 개수가 적고 간선의 개수가 많은 밀집 그래프(Dense Graph)의 경우에 적합하다.

3.2 인접 리스트(Adjacency List)

인접 리스트는 리스트를 이용해 그래프를 표현하는 방법이다. 인접 리스트는 다음과 같은 특징을 가진다.

adj_list = [[(3, 1)],
            [(1, 1), (2, 1)],
            [(1, 1), (2, 1), (3, 1), (4, 1)],
            [(0, 1), (2, 1), (3, 1)],
            [(2, 1), (4, 1)]]

인접 리스트는 다음과 같은 장단점을 가진다.

인접 리스트는 정점의 개수가 많고 간선의 개수가 적은 희소 그래프(Sparse Graph)의 경우에 적합하다.

Reference

2024-05-10
다음 글: 5월 2주차 알고리즘 문제 → 카테고리로 돌아가기 ↩