그래프(Graph)
그래프(Graph)는 정점(Vertex, Node)과 간선(Edge)의 집합으로 이루어진 자료구조로, 서로 복잡하게 얽혀있는 개체들의 N:M 관계를 표현할 수 있다. 정점(V)은 데이터를 담는 단위를 나타내며 간선(E)은 정점과 정점을 연결하는 관계를 의미한다. 예를들어 그래프로 네트워크망을 표현한다고 하면, 컴퓨터가 정점이 될 것이고 컴퓨터를 연결짓는 네트워크가 간선이 될 것이다.
정점의 차수 (degree)
차수(degree)는 정점에 직접 연결된 간선의 수를 의미한다. 무방향 그래프에서는 정점에 인접한 정점의 수를 말하며 위 사진에서 정점 1의 차수는 2이다. 방향 그래프에서는 외부에서 오는 간선의 수를 진입 차수(in-degree), 외부로 향하는 간선의 수를 진출 차수 (out-degree)라고 부른다.
경로(path)
경로(path)는 간선을 따라 갈 수 있는 길을 의미하며, 정점의 나열로 표시된다. 위 사진에서 정점 1부터 5까지의 경로는 ‘1,3,5’, ‘1,2,5’ 등이 있다. 이때 경로 중에서 반복되는 간선이 없는 경로를 단순 경로(simple path)라고 하며, 경로를 구성하는데 사용된 간선의 수를 경로의 길이라고 한다.
인접(Adjacent)과 연결(Connected)
인접(Adjacent)한다는 것은 정점과 정점이 간선에 의해 직접 연결되어있는 것을 의미한다. 하나의 정점에서 인접한 정점을 인접 정점(adjacent vertex)라고 부르며, 위 사진에서 정점 1의 인접 정점은 2, 3이다. 연결(Connected)은 정점에서 정점으로 가는 경로가 존재한다는 것을 의미한다. 위 사진에서 정점 1은 2, 3, 4, 5 정점과 모두 연결되어있다.
방향 그래프의 경우 간선에 방향이 존재하기 때문에 위 사진에서 1의 인접 정점은 1이며, 1은 2의 인접 정점이 아니다.
간선의 속성
그래프에서 간선은 단순히 연결 여부만 표현할 수도 있지만, 현실 세계의 문제를 모델링하려면 간선의 속성이 부여된다.
- 방향 (Direction)
- 가중치 (Weight) : 거리, 비용, 에너지, 점수 등 수치로 표현되는 값으로, 최단경로, 최소비용 문제에서 사용된다.
- 용량 (Capacity) : 네트워크 플로우(Flow Network)에서 사용되는 값으로, 한 간선을 통해 흘려보낼 수 있는 최대 흐름량을 의미한다. ex) 도로의 차선 수, 파이프의 유량 제한
- 흐름 (Flow) : 실제로 간선 위로 흘러가는 값.
- 신뢰도(Probability)/ 확률(Reliability) : 간선이 특정 확률로만 사용이 가능한 경우에 사용되는 값이다. ex) 네트워크 링크 장래 확률, 무선 통신 성공 확률
- 색 (Color) : 그래프 색칠 문제에서 등장한 값으로 간선을 색으로 구분해 제약 조건을 걸 때 사용한다.
- 라벨 (Label) : 간선에 문자열/ 심볼 같은 부가 정보를 붙이는 것. ex) “서울→부산”
- 시간 (Time, Delay) : 간선을 통과하는데 걸리는 시간
- 비용 (Cost) : 이동이나 작업에 필요한 자원으로 최단경로 문제(Dijkstra, Bellman-Ford)에서 자주 사용된다.
그래프의 종류
- 무방향 그래프 (undirected graph)와 방향 그래프(directed graph)
간선에 방향이 표시되지 않은 그래프를 무방향 그래프, 간선에 방향성이 존재하는 그래프를 방향 그래프라고 한다. 방향성이 있는 간선은 보통 화살표로 표시되는데 일방통행 도로와 마찬가지로 한쪽 방향으로만 갈 수 있음을 의미한다. 정점 A와 B를 연결하는 간선이 있다고 할때 무방향이라면 (A, B)와 (B, A)가 동일한 간선이지만 방향이 있다면 간선 <A,B>와 <B,A>는 다른 간선이다.
// 무방향 그래프 표현 - 간선 () V(G1) = {0, 1, 2, 3} E(G1) = {(0,1), (0,2), (0,3), (1,2), (2,3)} // 방향 그래프 표현 - 간선 <> V(G2) = {0, 1, 2} E(G2) = {<0,1>, <1,0>, <1,2>} - 비 가중치 그래프(unweighted graph)와 가중치 그래프(weighted graph)
간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프라고 한다. 가중치 그래프는 네트워크(network)라고도 부르며 간선은 두 정점간의 연결 유무 뿐만 아닌 연결 강도까지 나타낼 수 있어 보다 복잡한 관계를 표현할 수 있게 된다. 반대로 비 가중치 그래프는 비용이나 가중치가 없기 때문에 모든 간선에 동일한 비용이 들어 단순한 연결 관계를 표현한다. - 비 연결 그래프와 연결 그래프
모든 정점이 간선으로 연결 되어있는 그래프를 연결 그래프라고 하며, 일부 정점이 연결되지 않고 떨어져 있는 그래프를 비 연결 그래프라고 한다. - 순환 그래프(cyclic graph)와 비순환 그래프(acyclic graph)
그래프에서 하나의 정점에서 출발하여 다시 자기 자신으로 돌아오는 경로를 사이클(cycle)이라고 하며 이때 시작 정점을 제외한 중복 방문은 없어야한다. 이 사이클 여부에 따라 순환 그래프와 비순환 그래프로 나뉜다. - 트리
연결그래프 중 사이클이 없는 그래프 - 완전 그래프
모든 정점간에 간선이 존재하여 모두 연결되어있는 그래프를 의미하며, 무방향 완전 그래프의 정점 수를 n이라고 하면 하나의 정점은 n-1개의 다른 정점으로 연결되므로, 간선의 수는 n x (n-1)/2가 된다.
위상 정렬 (Topological Sort)
위상 정렬(topological sort)는 방향 그래프에서 모든 간선의 방향을 거스르지 않도록 정점을 나열하는 것이다. 이때 사이클이 있다면 순서를 정할 수 없기 때문에 위상 정렬은 불가능하다. 때문에 위상 정렬을 하기 위해서는 그래프가 반드시 DAG(Directed Acyclic ZGraph, 방향 비순환 그래프)이어야 한다. 위상 정렬은 방향을 따라 나열하는 것이 아닌, 방향을 거스르지 않고 나열하는 것이기 때문에 여러가지 결과가 나올 수 있다.
- 위상 정렬 방법
- 진입 차수 (Indegree) 기반 방법 (Kahns Algorithm)
진입 차수가 0인 정점을 큐에 넣고, 하나씩 꺼내서 해당 노드에서 나가는 간선을 제거하며(연결 노드들의 진입 차수 감소) 계속해서 진입차수가 0인 정점을 찾아 위 과정을 반복하는 방법 - DFS 기반 위상 정렬
DFS의 결과를 역순으로 꺼내 위상 정렬 결과를 얻는 방법
- 진입 차수 (Indegree) 기반 방법 (Kahns Algorithm)
희소 그래프와 조밀 그래프
| 구분 | 정의 | 특징 | 예시 |
| 조밀 그래프 | 간선 개수 E ≈ V² | 거의 모든 정점이 서로 연결 | 완전 그래프, 토너먼트 대진표 |
| 희소 그래프 | 간선 개수 E ≪ V² | 대부분의 정점이 연결되어 있지 않음 | SNS 친구 수, 도로망, 인터넷 링크 |
- 희소 그래프 → 간선 수 적음 → 메모리 효율적 구조 필요
- 조밀 그래프 → 간선 수 많음 → 접근 속도가 중요한 구조가 유리
그래프의 표현
1. 간선 리스트 (Edge List)
그래프의 모든 간선(Edge) 정보를 리스트나 배열로 저장하는 방법이다. (출발 정점, 도착 정점, 가중치)로 간선을 나타내며 (가중치가 없는 경우는 (출발정점, 도착정점))구조가 직관적이고 구현이 간단하다. 정점이 아닌 간선 정보만 저장하므로 정점에 비해 간선이 적은 희소그래프 처리에 유리하고 간선 배열을 가중치 기준으로 정렬할 수 있으므로 가공에도 용이하다. 하지만 정점끼리의 연결 여부를 확인하려면 전체 배열을 순회해야하고 BFS, DFS처럼 어떤 정점에서 출발하는 모든 간선을 찾을때도 전체 배열을 순회해야하기 때문에 간선 중심의 알고리즘에 적합한 저장 방식이다.
| 그래프 타입 | 공간 복잡도 | 간선 탐색 | 인접 노드 탐색 | 모든 간선 순회 | 간선 추가 | 간선 삭제 |
| 희소 그래프 (적합) | O(E) | O(E) | O(E) | O(E) | O(1) | O(E) |
| 조밀 그래프 | O(E) ≈ O(V²) | O(E) ≈ O(V²) | O(E) ≈ O(V²) | O(E) ≈ O(V²) | O(1) | O(E) ≈ O(V²) |
2. 인접 행렬 (Matrix)
정점(V) 개수만큼 [v][v] 2치원 배열을 만들어 matrix[u][v]에 간선 정보를 저장하는 방법이다. 가중치가 없는 경우는 간선이 있다면 1, 없다면 0을 저장한다. 만약 가중치가 있다면 가중치를 저장한다. 무방향 그래프의 경우 행렬은 대칭이 되기 때문에 배열의 상위 삼각이나 하위 삼각만 저장하면 메모리를 절약할 수 있다. 두 노드의 간선 여부를 확인할때는 인덱스로 바로 접근이 가능하며, 한 정점에서 연결된 간선을 찾으려면 한 행을 모두 탐색해야하기 때문에 n번 순회해야한다. 하지만 희소그래프처럼 노드에 비해 연결된 간선이 적다면 메모리 낭비의 단점이 있다.
| 그래프 타입 | 공간 복잡도 | 간선 탐색 | 인접 노드 탐색 | 모든 간선 순회 | 간선 추가 | 간선 삭제 |
| 조밀 그래프 (적합) | O(V²) | O(1) | O(V) | O(V²) | O(1) | O(1) |
| 희소 그래프 | O(V²) → 낭비 | O(1) | O(V) | O(V²) | O(1) | O(1) |
3. 인접 리스트 (Adjacent List)
각 정점마다 인접 정점들을 연결 리스트로 저장하고 이 인접 리스트에 대한 헤더 포인터를 배열로 관리하는 방식이다. 정점의 개수가 n개이고, 간선의 수가 e인 무방향 그래프를 표현하기 위해서는 n개의 연결 리스트가 필요하고 n개의 헤더포인터와 2e개의 노드가 필요하다. 따라서 인접 리스트는 정점의 개수에 비해 간선의 개수가 매우 적은 희소 그래프의 표현에 매우 유리하다. 또 정점 기준 탐색 방식인 BFS, DFS구현이 간단하고 빠르며 간선의 추가 삭제 비용이 적게 들어 동적 그래프 수정이 용이하다. 하지만 두 정점간의 간선 여부 확인이 느리며 간선을 기준으로 한 정렬/ 검색을 위해서는 리스트를 따로 합쳐야 한다.
| 그래프 타입 | 공간 복잡도 | 간선 탐색 | 인접 노드 탐색 | 모든 간선 순회 | 간선 추가 | 간선 삭제 |
| 조밀 그래프 | O(V + E) ≈ O(V²) | O(degree(u)) ≈ O(V) | O(degree(u)) ≈ O(V) | O(V + E) ≈ O(V²) | O(1) | O(degree(u)) ≈ O(V) |
| 희소 그래프 (적합) |
O(V + E) | O(degree(u)) | O(degree(u)) | O(V + E) | O(1) | O(degree(u)) |
'CS > 자료구조, 알고리즘' 카테고리의 다른 글
| [알고리즘] 위상 정렬 알고리즘(Topological Sort Algorithm) - 멀티 스레드를 활용한 Task 스케줄링 병렬 처리 (0) | 2025.10.31 |
|---|---|
| [알고리즘] 다익스트라(Dijkstra) 최단 경로 알고리즘 (0) | 2025.10.20 |
| [알고리즘] 슬라이딩 윈도우(Sliding Window) 알고리즘과 단조 큐(Monotonic Queue) (0) | 2025.09.19 |
| [알고리즘] 'N의 연속된 자연수의 합 찾기'와 투 포인터(Two Pointers) 알고리즘 (0) | 2025.09.18 |
| [알고리즘] 구간합(Query of Range Sum)과 누적합 알고리즘(Prefix Sum) (0) | 2025.09.18 |