[자료구조] 그래프(Graph) 와 위상 정렬(Topological Sort)

 

자료구조는 크게 선형 구조, 계층적 구조, 그리고 그래프 구조로 나눌 수 있다.

배열이나 리스트 같은 선형 구조는 1:1 관계를, 트리와 같은 계층 구조는 1:N 관계를 표현한다.

하지만 현실 세계의 관계는 이보다 훨씬 더 복잡하다. 도시와 도시를 잇는 도로망이나 사람과 사람의 친구 관계처럼 N:M 관계가 일반적이다. 이러한 복잡한 연결을 표현하기 위해 사용되는 자료구조가 바로 그래프(Graph) 이다.

 

이번 글에서는 그래프의 기본 개념과 특징, 그리고 다양한 표현 방식을 정리해 보려고 한다.

 

 

 

0. 자료구조의 구조적 차이

1. 선형 자료구조 (Linear Structure)

원소들이 순차적으로 일렬로 나열된 구조

• 특징: 각 원소가 앞뒤 원소와만 관계를 가짐 (1:1 관계)
• 예시: 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue)
• 사용처: 데이터 순차 접근, 단순한 삽입/삭제, 순서 있는 처리

 

2. 계층적 자료구조 (Hierarchical Structure, 트리)

한 요소(부모)가 여러 요소(자식)와 연결될 수 있는 구조

• 특징: 부모-자식 관계로 이루어져 있으며 1:N 관계를 표현
• 예시: 트리(Tree), 이진 트리(Binary Tree), 힙(Heap)
• 사용처: 계층적 데이터 표현 (폴더 구조, 조직도, XML/JSON 파싱 등)

 

3. 그래프 자료구조 (Graph Structure)

정점(Vertex)과 간선(Edge)으로 이루어져, 정점 간의 N:M 관계를 표현할 수 있는 구조

• 특징: 하나의 노드가 여러 노드와 연결될 수 있고, 동시에 여러 노드가 같은 노드와 연결될 수도 있음
• 예시: SNS 친구 관계, 도로망, 네트워크 구조
• 사용처: 최단 경로 탐색, 네트워크 분석, 의존성 관계 처리

 

4. 비교

구조	연결 관계	예시 자료구조	현실 세계 예시
선형 구조	1:1	배열, 연결 리스트, 스택, 큐	기차 칸(앞뒤로만 연결)
계층 구조	1:N	트리, 이진 트리, 힙	회사 조직도, 폴더 구조
그래프 구조	N:M	그래프(인접행렬, 인접리스트)	도로망, SNS, 인터넷

 

선형 구조는 순서를,
계층 구조는 계층 구조 (부모-자식 관계)를,
그래프는 복잡한 연결 관계(네트워크)를 표현하는 데 적합하다. 

 

 

 

 

 

 

1. 그래프 (Graph)

그래프는 정점(Vertex)과 간선(Edge)의 집합으로 이루어진 자료구조이며, 정점 간의 N:M 관계를 표현하는 비선형 구조이다.

 

• 정점(Vertex) : 데이터를 담는 단위 (예: 도시, 사람, 컴퓨터)
• 간선(Edge) : 정점과 정점을 잇는 관계 (예: 도로, 친구 관계, 네트워크 연결)

 

 

2. 수학적 정의 

V	정점의 집합 (Vertices)
E ⊆ V×V	간선의 집합 (Edges)

 

 ×   (곱)           : 정점 집합 V와 V의 데카르트 곱(Cartesian product) , 즉, 가능한 모든 정점 쌍의 집합

 ⊆ (부분집합) : 간선 집합 E는 이 모든 가능한 정점 쌍 중에서 일부만 선택 된 것. 

 

 

원소 개수 = ∣V∣×∣V∣
여기서는 ∣V∣= 5, 따라서 ∣V×V∣=25.
즉, 가능한 쌍은 총 25개.

 

 

 

3. 간선의 속성

그래프에서 간선(Edge) 은 단순히 "연결 여부"만 표현할 수도 있지만, 현실 세계의 문제를 모델링하려면 간선의 속성이 부여된다.

속성
가중치(Weight)	거리, 비용, 에너지, 점수 등 수치로 표현되는 값 : 최단 경로, 최소 비용 문제에서 사용
방향(Direction)	무방향 그래프 : 간선 (u,v) = (v,u) → 상호 연결 방향 그래프(Directed Graph) : 간선 (u,v) ≠ (v,u) → 일방향 연결
용량(Capacity)	네트워크 플로우(Flow Network)에서 사용 : 한 간선을 통해 흘려보낼 수 있는 최대 흐름량 예: 도로의 차선 수, 파이프의 유량 제한
흐름(Flow)	실제로 간선 위로 흘러가는 값 용량(capacity)과 구분됨 (예: 파이프 용량은 100L/s인데 실제 흐름은 70L/s)
신뢰도/확률 (Probability / Reliability)	간선이 특정 확률로만 사용 가능한 경우 예: 네트워크 링크 장애 확률, 무선 통신 성공 확률
색(Color)	그래프 색칠 문제에서 등장 간선을 색으로 구분해 제약 조건을 걸 때 사용
라벨(Label)	간선에 문자열/심볼 같은 부가 정보를 붙이는 것 예: “서울 → 부산 (KTX)” vs “서울 → 부산 (버스)”
시간(Time / Delay)	간선을 통과하는 데 걸리는 시간 예: 네트워크 지연시간, 교통 소요시간
비용(Cost)	이동이나 작업에 필요한 자원(돈, 에너지 등) 최단경로 문제(Dijkstra, Bellman-Ford)에서 자주 사용

 

3-1. 예시  (서울 ↔ 부산 그래프)

• 정점 속성 : Vertices = {서울(population=10M), 부산(population=3M)}
• 간선 속성 : Edge (서울 → 부산):
  • 방향 = 양방향
  • 가중치 = 400km (거리)
  • 비용 = 50,000원 (KTX 요금)
  • 시간 = 2시간 30분
  • 라벨 = "KTX"

 

 

4. 간선의 인접과 연결

4-1. 인접(Adjacent)

인접 : 두 정점이 직접 간선으로 연결되어 있을 때, 인접 하다고 함. 

• 방향 그래프(Directed Graph) 에서는 간선 방향을 따라야 함
  • 간선이 u→v이면 : u에서 v는 인접 (v에서 u는 아님)

즉, “바로 옆에 붙어 있음” 의 의미

 

 

4-2. 연결(Connected / Reachable)

연결 : 두 정점 사이에 경로(Path) 가 존재할 때 

• 여러 정점을 거쳐도 도달 가능하면 연결되었다고 함. 
  • 방향 그래프라면 반드시 화살표 방향을 따라가야 연결로 인정됨.
  • 예: u → x → y → v 경로가 있으면 u와 v는 연결됨.

 즉, “경로를 따라가서 도달 가능하다면” 연결 

 

인접은 "바로 붙어 있음", 연결은 "갈 수 있음"의 차이

 

 

 

5. 노드의 차수(Degree)

정점(Vertex, Node)에 연결된 간선(Edge)의 개수를 그 정점의 차수라고 한다.

 

• 특징 (무방향 그래프, 방향 그래프 동일)

모든 정점 차수의 합 = 간선 수 × 2

 

• 활용: 그래프 검증, 알고리즘 분석, 오일러 회로, 네트워크 분석 등

 

 

 

 

 

6. 위상 정렬 (Topological Sort)

위상 정렬을 하려면 그 그래프는 반드시 DAG(Directed Acyclic Graph, 비순환 방향 그래프) 이어야 한다.

사이클(Cycle)이 있으면 순서를 정할 수 없음 (예: A→B, B→C, C→A)

 

 

6-0. DAG (비순환 방향 그래프)

DAG (비순환 방향 그래프) 는 사이클이 없는 그래프이다. 

왼쪽은 DAG / 오른쪽은 사이클이 있으므로 DAG가 아님

 

 

6-1. 위상 정렬 (Topological Sort)

DAG (비순환 방향 그래프)에서 정점들을 방향을 거스르지 않도록 선형으로 정렬( Linear Ordering ) 하는 것이다. 

• 즉, u → v 에서 무조건 u가 v보다 먼저 나와야 함

 

6-2. 결과

위상 정렬의 결과는 하나가 아닐 수도 있음  ( 동시에 시작 가능한 노드가 있으면 여러 순서 가능 ) 

DAG

Topological order

 

위상 정렬 결과 하나의 DAG에서 하나 이상의 위상 순서(Topological order)가 나올 수 있으며 모든 간선은 오른쪽만 가리키게 된다.

 

위상 정렬은 DAG에서 정점들을 선행 조건(간선 방향)을 지키며 나열하는 정렬 방식으로, 
작업 스케줄링, 컴파일 순서, 렌더링 패스 실행 순서 등 다양한 의존성 문제가 있는 곳에서 활용된다.

 

 

 

 

7. 그래프 표현

7-1. 간선 목록(Edge list)

간선(edge) 중심으로 존재하는 간선으로 그래프 표현.

• 간선 중심의 알고리즘에 적합하다.

• 장점
  1. 메모리 효율적 : 필요한 간선만 저장하므로, 노드 수보다 간선의 수가 적은 희소 그래프(Sparse Graph)에 유리
  2. 정렬 및 가공 용이 : 간선 배열을 가중치 기준으로 정렬 가능.
  3. 단순 구조 : 출발, 도착, 속성만 있으면 되므로 구조가 직관적.
• 단점 
  1. 연결 여부 확인이 느림 : 두 정점 (u,v)가 연결되어 있는지 확인하려면 전체 간선 배열을 순회해야 함
  2. 정점 기준 탐색이 불편 :  BFS, DFS처럼 어떤 정점에서 출발하는 모든 간선을 찾으려면 배열 전체를 검색해야 함.

 

 

 

7-2. 인접 행렬 

노드 중심으로 모든 노드 관계를 그래프 표현하기

• 연결 여부 빠른 확인이 필요할때 유리하다.

• 장점
  1. 두 노드의 간선 속성을 인덱스로 바로 접근 가능하다
• 단점 
  1. 특정 노드와 연결된 간선을 찾기 위해 N번 확인 해야 한다.  
  2. 또한,  노드 수보다 간선의 수가 적은 희소 그래프(Sparse Graph)라면, 메모리가 비효율적이다

 

 

 

7-1. 인접 리스트 

노드 중심의 인접한 노드 정보로 그래프를 표현

• 탐색(BFS, DFS) 에 강점이 있다.

• 장점
  1. 메모리 효율적 : 희소 그래프(Sparse Graph, 간선이 적은 경우)에 매우 유리
     • 공간 복잡도 : O(N+M)   (N = 정점 수, M = 간선 수) 
  2. 정점 기준 탐색에 적합 : BFS, DFS 구현이 간단하고 빠름
  3. 동적 그래프 수정 용이 : 간선 추가 / 삭제가 비교적 효율적

• 단점 
  1. 두 정점 간 연결 여부 확인이 느림
     • “u와 v가 연결되어 있는가?” 확인하려면 리스트를 순회해야 함
     • 최악의 경우 O(deg(u))
     • 인접 행렬은 O(1)에 확인 가능
  2. 간선 정렬 / 검색 불편
     • 간선을 특정 기준(예: 가중치)으로 정렬하려면 리스트를 따로 합쳐야 함
     • 간선 기반 알고리즘에는 불리
  3. 구현 복잡도
     • 인접 행렬보다 구조가 복잡함
     • 특히 다중 그래프(같은 두 정점 사이에 여러 간선이 있는 경우)나 방향 그래프일 때 관리가 번거로움

 

 

 

8. 정리

항목	정의/설명	특징/활용
그래프(Graph)	정점(Vertex)과 간선(Edge)으로 이루어진 자료구조	현실 세계의 복잡한 관계(네트워크)를 모델링
인접(Adjacent)	두 정점이 직접 연결되어 있는 경우	"바로 옆에 붙어 있음" 의미
연결(Connected)	두 정점 사이에 경로(Path) 가 존재하는 경우	여러 간선을 거쳐도 도달 가능
차수(Degree)	정점에 연결된 간선 수	네트워크 구조 분석, 알고리즘 검증, 오일러 경로 판정 등
위상 정렬(Topological Sort)	DAG에서 간선 방향을 지키며 정점 순서를 정리	작업 스케줄링, 의존성 분석에 활용
그래프 표현 방법	- 간선 목록(Edge List) - 인접 행렬(Adjacency Matrix) - 인접 리스트(Adjacency List)	- 간선 목록: 희소 그래프, 정렬/가공 유리 - 인접 행렬: 연결 여부 빠른 확인 - 인접 리스트: 탐색(BFS/DFS) 효율적,                       메모리 효율적, 동적 그래프 처리 유리