안녕하세요! 지난 포스팅에서는 그래프의 기본 개념과 그래프로 할 수 있는 것에 대해 살펴보았습니다. 오늘은 그래프를 구현하는 2가지 방법에 대해 알아보고, 그래프 알고리즘을 활용하여 풀 수 있는 다양한 문제들을 소개해 드리겠습니다.
인접 행렬 개념과 구현
그래프를 코드로 표현하기
그래프라는 추상적인 개념을 실제 코드로 구현하는 방법은 여러 가지가 있습니다. 그중에서도 가장 쉽고 직관적인 방법은 인접 행렬(Adjacency Matrix) 입니다. 인접 행렬은 2차원 배열을 사용하여 그래프의 연결 관계를 표현합니다.
인접 행렬의 기본 개념
인접 행렬은 N × N 크기의 2차원 배열로, N은 그래프의 노드 수입니다. 행렬의 각 원소 matrix[i][j]는 노드 i에서 노드 j로 가는 엣지의 존재 여부를 나타냅니다:
- 무방향 그래프: matrix[i][j] = matrix[j][i] = 1 (엣지가 있는 경우)
- 방향 그래프: matrix[i][j] = 1 (i에서 j로 가는 엣지가 있는 경우)
- 가중치 그래프: matrix[i][j] = weight (i와 j 사이의 가중치)
- 연결이 없는 경우: matrix[i][j] = 0 또는 무한대(∞)
인접 행렬의 장단점
장점
- 구현이 간단합니다: 2차원 배열만 있으면 쉽게 구현할 수 있습니다.
- 엣지 확인이 빠릅니다: 두 노드 간 연결 여부를 O(1) 시간에 확인할 수 있습니다.
- 그래프 표현이 직관적입니다: 행렬을 보면 그래프의 전체 구조를 한눈에 파악할 수 있습니다.
단점
- 메모리 사용량이 많습니다: 노드 수의 제곱(N²)에 비례하는 메모리가 필요합니다.
- 희소 그래프에 비효율적입니다: 엣지가 적은 그래프의 경우 많은 공간이 낭비됩니다.
- 모든 이웃을 찾는 데 O(N) 시간이 필요합니다: 노드의 모든 연결을 확인하려면 전체 행(또는 열)을 검사해야 합니다.
인접 리스트 개념과 구현
인접 리스트는 그래프를 표현하는 방법 중 하나로, 각 정점에 인접한 정점들을 리스트 형태로 저장하는 방식입니다. 이 방법은 특히 간선의 수가 정점의 수에 비해 상대적으로 적은 희소 그래프(Sparse Graph)에서 매우 효율적입니다.
인접 리스트의 개념
인접 리스트는 각 정점마다 해당 정점과 연결된 다른 정점들의 목록을 저장합니다. 예를 들어, 정점 0이 정점 1, 2, 3과 연결되어 있다면, 정점 0의 인접 리스트는 [1, 2, 3]이 됩니다. 이러한 구조는 배열, 연결 리스트, 벡터 등 다양한 자료구조를 통해 구현할 수 있습니다.
기본 구현 방법
인접 리스트를 구현하는 가장 일반적인 방법은 각 정점마다 하나의 리스트를 할당하는 것입니다. 이 리스트는 해당 정점과 연결된 모든 정점들을 포함합니다. 프로그래밍 언어에 따라 배열의 배열, 연결 리스트의 배열, 또는 벡터의 벡터 등으로 구현할 수 있습니다.
가중치/방향/무방향 그래프 구현
무방향 그래프의 경우, 두 정점 u와 v가 연결되어 있으면 정점 u의 리스트에 v를 추가하고, 정점 v의 리스트에도 u를 추가합니다. 방향 그래프에서는 간선의 방향에 따라 한쪽 방향으로만 정점을 추가합니다.
가중치 그래프의 경우, 각 리스트에 인접 정점뿐만 아니라 해당 간선의 가중치도 함께 저장해야 합니다. 이를 위해 (인접 정점, 가중치) 형태의 쌍을 리스트에 저장합니다. 아래는 파이썬으로 작성한 간단한 인접 리스트 구현입니다. 편의상 정점이 1부터 시작한다고 가정했습니다.
인접 행렬과 인접리스트의 차이점
그래프를 표현하는 두 가지 주요 방식인 인접 행렬과 인접 리스트는 각각 고유한 특성과 장단점을 가지고 있습니다. 대부분의 경우 인접 리스트를 구현하겠지만 인접 행렬도 장점이 있습니다.
메모리 사용량 비교
인접 행렬은 V×V 크기의 2차원 배열을 사용합니다(V는 정점의 수). 이는 그래프의 모든 가능한 간선에 대한 정보를 저장하므로 V²에 비례하는 메모리를 사용합니다. 반면, 인접 리스트는 실제로 존재하는 간선만 저장하기 때문에 V+E에 비례하는 메모리를 사용합니다(E는 간선의 수).
따라서 희소 그래프(간선이 적은 그래프)의 경우 인접 리스트가 메모리 효율성 측면에서 훨씬 유리합니다. 하지만 밀집 그래프(간선이 많은 그래프)에서는 두 방식의 메모리 사용량 차이가 크지 않을 수 있습니다.
시간 복잡도 분석
두 방식은 수행하는 연산에 따라 시간 복잡도가 달라집니다:
- 간선 확인: 인접 행렬은 O(1)로 두 정점 사이의 간선 존재 여부를 확인할 수 있습니다. 인접 리스트는 최악의 경우 O(V)가 소요됩니다.
- 정점의 모든 인접 정점 탐색: 인접 행렬은 항상 O(V)가 소요됩니다. 인접 리스트는 해당 정점의 차수(정점과 연결되어 있는 정점의 수)에 비례하여 O(차수)가 소요됩니다.
- 그래프 전체 탐색: 인접 행렬은 O(V²)가 소요되지만, 인접 리스트는 O(V+E)가 소요됩니다.
상황별 적합한 구현 방식 선택
인접 행렬은 다음과 같은 상황에서 유리합니다:
- 두 정점 간의 간선 존재 여부를 자주 확인해야 하는 경우
인접 리스트는 다음과 같은 상황에서 유리합니다:
- 희소 그래프 (E << V²)
- 그래프 전체를 탐색해야 하는 경우(BFS, DFS)
- 모든 간선을 순회해야 하는 경우
- 메모리 사용량이 중요한 경우
결론적으로, 많은 그래프 알고리즘에서는 인접 리스트가 더 효율적인 경우가 많지만, 상황에 따라 인접 행렬이 더 적합할 수도 있습니다.
오늘은 그래프 구현의 핵심인 인접 리스트에 대해 알아보고, 인접 행렬과의 차이점을 비교했으며, 주요 그래프 알고리즘들을 살펴보았습니다. 그래프 알고리즘은 컴퓨터 과학의 중요한 부분이며, 네트워크 분석, 경로 찾기, 데이터 마이닝 등 다양한 분야에서 활용됩니다.
앞서 소개한 추천 문제들을 이후 포스팅에서 자세한 구현 방법을 알아볼 것입니다. 직접 풀어보면서 그래프 이론과 알고리즘을 실전에서 적용해 보는 것을 권장합니다. 특히 BFS와 DFS를 활용한 문제들은 그래프의 기본을 이해하는 데 큰 도움이 될 것입니다.
그래프 알고리즘에 대한 질문이나 더 알고 싶은 주제가 있으면 댓글로 남겨주세요. 감사합니다!