[이론] 그래프 (Graph)

 

그래프(Graph)는 노드와 간선으로 이루어진 자료구조로, 객체 간의 관계를 표현하며 다양한 응용 분야에서 사용된다. 주로 탐색 알고리즘에는 BFS, DFS가 있고, 최단 경로와 최소 신장 트리 등 다양한 그래프 알고리즘에 활용된다. 오늘은 코딩 테스트에서 자주 등장하는 자료구조인 그래프에 대해 알아보도록 하겠다.

 

---

그래프 (Graph) 정의

 

그래프(Graph): 노드와 간선으로 이루어진 자료구조

 

그래프는 데이터 구조의 일종으로, 객체 간의 관계를 나타내는 데 사용된다.

노드(Node, 또는 Vertex)와 간선(Edge)으로 구성되며, 두 노드 간의 연결을 나타낸다.

주로 소셜 네트워크 및 지도 경로 탐색, 웹 페이지 간의 링크 구조, 게임 월드 맵 등에 주로 사용된다.

 

💡  노드(Node): 그래프에서 데이터 혹은 객체를 나타내는 기본 단위이다.

💡 간선(Edge): 두 노드 간의 관계를 나타낸다.

 

 

 

---

그래프의 종류

 

그래프의 종류는 크게 간선 방향의 유무와 가중치의 유무로 판별할 수 있다.

• 무방향 그래프
• 방향 그래프
• 가중치 그래프
• 비가중치 그래프

대표적으로 위 4가지 그래프가 코팅 테스트에 주로 등장하는 형태이다.

그 외 그래프의 종류에 대해 더 궁금하다면 아래 더보기를 참고하라.

Simple Graph: 각 노드 쌍 간에 최대 하나의 간선만 존재하는 그래프이다. 즉, 두 노드 사이에 중복된 간선이 없고, 자기 자신을 가리키는 루프(Loop)도 없는 평태이다. 주로 대부분의 그래프 알고리즘은 Simple Graph를 기반으로 한다.

 

Multi Graph: 두 노드 간에 여러 개의 간선이 존재할 수 있는 그래프이다. 즉, 두 노드 사이에 여러 간선이 연결될 수 있다. 지도를 기반으로 한 교통 네트워크에서 주로 사용한다.

 

Pseudo Graph: 자기 자신과 연결되는 루프를 포함하는 Multi Graph로, 좀 더 포괄적인 형태이다. 소셜 네트워크의 복잡한 관계에서 주로 사용한다.

 

Complete Graph: 모든 노드가 최대 개수의 Edge를 가지는 그래프이다.

 

Cycle Graph: 모든 노두가 하나의 Sequence로 연결되면서 처음과 끝 노드가 다시 연결된 형태의 그래프이다. 주로 순환 구조를 가진 Round Robin 알고리즘에 사용된다.

 

Wheel Graph: Cycle Graph에 중심 노드를 추가하여 모든 외곽 노드와 연결한 그래프이다. 주로 네트워크의 중앙 집중형 구조를 모델링하는데 사용한다.

 

Cube Graph: 2^n개의 노드가 n-차원 하이퍼큐브 형태로 연결된 그래프이다. 주로 병렬 컴퓨팅에서의 프로세서 연결, 데이터베이스 관계 표현 등에 사용된다.

 

Bipartite Graph: 노드들이 두 개의 독립된 집합으로 나뉘며, 같은 집합 내의 노드들끼리는 연될되지 않고 서로 다른 집합의 노드들 간에만 간선이 존재하는 그래프이다. 주로 소셜 네트워크에서 사용자와 관심사 간의 관계, 팀 간의 매칭 문제 등에서 활용된다.

 

 

 

---

Outdegree & Indegree

 

 

indegree와 outdegree는 방향 그래프에서 각 노드의 연결 상태를 나타내는 중요한 개념이다.

각 노드마다 indegree & outdegree를 가지고 있다.

 

InDegree: 노드로 들어오는 간선의 수

OutDegree: 노드에서 나가는 간선의 수

 

주로 그래프의 성질을 분석하거나 특정 노드의 중요성을 평가할 때 사용한다.

특히, 위상 정렬(Topological Sort)나 페이지랭크 알고리즘 등에서 사용되는 중요한 개념이다.

 

 

 

---

그래프 표현 방식: 인접 행렬

 

인접 행렬: 그래프의 노드 간 연결 상태를 2차원 배열로 나타낸 방식이다.

 

인접 행렬의 구조

• 노드 개수가 n이라면 n x n 크기의 2차원 배열로 구성
• 행과 열의 인덱스로 노드를 표현 (예: A - B 간선 표현은 array[A][B] = 1)
• 가중치가 있는 그래프라면 array[A][B]에 가중치를 저장하고, 연결되지 않았다면 무한대(∞)로 저장

 

인접 행렬의 장점

• O(1)의 시간으로 간선을 빠르게 탐색
• 간선을 빠르게 수정

 

인접 행렬의 단점

• 공간 복잡도는 O(n^2)로 메모리 효율이 낮음
• 연결된 노드를 찾으려면 전체 배열을 확인해야 하므로 탐색 비효율 O(n)

 

인접 행렬은 빠르게 특정 연결을 확인할 필요가 있는 정적 그래프에서 유리하다.

 

💡 인접 행렬 사용 알고리즘: 플로이드워셜 

 

 

 

---

그래프 표현 방식: 인접 리스트

 

인접 리스트: 그래프의 각 노드와 연결된 이웃 노드들을 리스트 형태로 저장하는 방식이다.

 

인접 리스트의 구조

• 그래프의 각 노드에 대해 리스트를 할당
• 각 노드는 자신과 연결된 이웃 노드의 리스트를 저장

 

인접 리스트의 장점

• 공간 복잡도는 O(n + e)로 메모리 효율이 좋음
• 이웃 노드를 확인하거나 순회하기에 효율이 좋음

 

인접 리스트의 단점

• 두 노드 간의 간선 존재 여부를 확인하는 데 시간이 오래 걸림 (최악: O(n))
• 간선을 추가/삭제할 때 시간이 오래 걸림

 

인접 리스트는 연결된 이웃을 효율적으로 관리하고 탐색하는 데 적합한 자료 구조이다.

특히 희소 그래프에서 메모리와 성능 면에서 효율적이다.

 

💡 인접 리스트 사용 알고리즘: 다익스트라, 벨만포드, 최소 신장 트리, 위상 정렬

 

---

정리

그래프는 노드와 간선으로 구성된 기본적인 자료 구조이지만, 이를 통해 다양한 구조와 관계를 나타낼 수 있어 중요한 자료구조로 간주된다. 앞으로 그래프 자료구조를 통해 어떤 알고리즘이 등장했는지 살펴보도록 하겠다.