[알고리즘] 그래프: 이해와 활용하는 자료구조

그래프는 현대의 정보 시대에서 다양한 분야에서 활발히 사용되는 중요한 자료구조입니다. 이 글에서는 그래프의 기본 개념과 그래프를 활용하는 방법에 대해 알아보겠습니다. 또한, 이를 통해 다양한 분야에서 그래프가 어떻게 활용되는지에 대해 살펴보겠습니다.

그래프의 기본 개념

그래프는 노드(정점)와 간선(엣지)으로 이루어진 자료구조입니다. 이 노드들은 서로 연결되어 있으며, 이 연결 관계가 그래프의 핵심입니다. 무방향 그래프는 간선에 방향이 없는 경우이며, 양쪽으로 이동할 수 있습니다. 반면에 유향 그래프는 간선에 방향이 있는 경우로, 한 방향으로만 이동할 수 있습니다.

Adjacency
정점을 연결하는 모서리가 있는 경우 정점이 다른정점과 인접하다고 함

Path(경로)
정점 A에서 정점 B로 이동할 수 있는 일련의 가장자리 경로

Undirected Graph (무방향 그래프)
- 그래프에서 간선에 방향이 없는 경우
- 간선은 양쪽으로 이동 가능, 매트릭스 표현에서는 대칭
- 즉, A에서 B로 가는 간선이 있다면, B에서 A로 가는 간선도 있음

Directed Graph (유향 그래프)
- 그래프에서 간선에 방향이 있는 경우
- 간선은 한 방향으로만 이동할 수 있음
- A에서 B로 가는 간선이 있을 때, B에서 A로 가는 간선이 반드시 존재하지 않음

 

그래프의 구현 방법

그래프는 다양한 방식으로 구현될 수 있습니다. 인접 행렬은 그래프를 행렬로 나타내는 방법으로, 간선의 존재 여부를 행렬의 요소로 표현합니다. 또한, 연결 리스트는 각 노드의 인접한 노드들을 연결하여 표현하는 방법입니다.

 

인접행렬

 

인접 행렬에서  'a[i][j] = 1' 는 간선(edge)이 존재합니다. 'a[i][j] = 0'는  간선이 존재하지 않습니다.

제공된 이미지와 설명에 따르면, 이는 무방향 그래프(undirected graph) 입니다.
무방향 그래프의 특징 중 하나는 그래프가 대칭 합니다. 인접 행렬에서 a[i][j]가 1이라면 a[j][i]도 1이어야 함을 의미 합니다.
노드 i와 노드 j 사이에 양방향으로 간선이 존재함을 의미합니다.

 

인접행렬의 장점은 특정한 두 정점 사이에 간선이 존재하는지의 여부를 빠르게 확인할 수 있습니다. (O(1) 시간 복잡도).
단점은 그래프에 간선이 많지 않은 희소 그래프(sparse graph)의 경우 공간 낭비가 심합니다. 또한 모든 가능한 정점 쌍에 대해 공간을 할당해야 하므로, 정점의 수가 많으면 많을수록 때에따라 메모리 사용이 비효율적이 될 수 있습니다.

linkedlist 배열

Linkedlist 배열로 그래프를 나타냅니다. 배열의 인덱스는 Verticle 나타냅니다. 연결된 목록의 각 요소 Verticle과 인접한 Edge와 연결된 Verticle을 나타냅니다.
연결리스트는 각요소가 데이터와 다음요소를 가리키는 포인터로 구성된 선형데이터 구조입니다.

그래프의 활용 사례

그래프는 네트워크 분석, 최단 경로 찾기, 데이터베이스 쿼리 최적화 등 다양한 분야에서 활용됩니다. 예를 들어, 지리 정보 시스템에서는 도로망을 그래프로 표현하여 최단 경로를 찾거나 교통 정보를 분석합니다.

마무리

그래프는 현대의 정보 시대에서 매우 중요한 자료구조로, 다양한 분야에서 활용되고 있습니다. 이를 통해 다양한 문제를 해결하고, 새로운 인사이트를 발견할 수 있습니다. 그래프의 기본 개념을 이해하고, 다양한 활용 사례를 살펴보면서 그래프의 중요성을 깨닫게 됩니다.