10.3 인접 행렬을 이용한 깊이 우선 탐색

깊이 우선 탐색(Depth First Search)은 그래프의 한 정점에서 다른 정점으로 갈 수 있는 경로를 찾는 방법 중에 하나입니다. 하나의 정점에서 갈 수 있는 이웃 정점을 방문하고 다시 방문한 정점에서 이웃 정점을 방문하면서 원하는 목적 지점까지 방문하는 방법이예요. 이 때 방문했었던 정점을 다시 방문하지 말아야 합니다.

깊이 우선 탐색처럼 그래프에서 어떠한 문제를 해결하기 위해서는 그래프를 먼저 표현할 수 있어야 합니다. 정점의 개수가 비교적 적을 때는 인접행렬로 표현할 수 있습니다. 만약 정점의 개수가 많다면 인접 행렬은 이웃하지 않는 간선을 위한 영역도 포함하여 메모리 및 성능이 나빠집니다. 이럴 때는 정점과 간선의 집합으로 그래프를 표현하여 문제를 해결할 수 있습니다.

여기에서는 인접 행렬을 이용하여 그래프를 표현하는 것을 먼저 구현한 후에 정점과 간선의 집합으로 그래프를 표현하는 방법을 살펴보기로 할게요.

다음은 방향성 없는 그래프를 표현한 하나의 예입니다.방향성 없는 그래프

그리고 이를 인접행렬로 표현한 예입니다.방향서 없는 그래프를 인접 행렬로 표현