본 시리즈는 프로그래밍 자료구조의 개념을 정리하고 실습을 진행해보는 시리즈입니다.
- 실습은 다음과 같은 개발환경 및 버전에서 진행하였습니다.
- IDE : IntelliJ IDEA (Ultimate Edition)
- Java : JDK 21 (corretto-21)
- Python : 3.9 (conda env)
비선형 자료구조 - Graph (Part 2)
지난 포스팅에서 그래프의 기본 개념과 그래프를 구성하는 요소들, 그리고 그래프의 다양한 분류에 대해 다뤘습니다.
이번 포스팅에서는 프로그래밍 언어(Java, Python)에서의 그래프 표현 방법과 구현 방법에 대해 다루고, 그래프를 활용하는 알고리즘 예시들을 간단하게 소개하는 시간을 가져보려합니다.
- 알고리즘의 구체적인 내용들은 알고리즘 파트에서 따로 다룹니다
4. Graph의 표현 방법
그래프는 주로 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)를 사용하여 표현됩니다.
- 각 표현 방법은 그래프의 구조에 따라 장단점이 다르므로, 상황에 맞게 선택해야 합니다.
4.1 인접 행렬 (Adjacency Matrix)
인접 행렬은 그래프의 정점들 간의 연결 관계를 2차원 배열로 표현하는 방법입니다.
- 행(row)과 열(column)은 각각의 정점을 나타내며, 특정 정점
i에서 정점j로 간선이 존재하는 경우, 배열의 값을1(또는 가중치가 있을 경우가중치 값)로 설정합니다. 간선이 없으면 값은0입니다.
장점
- 간선의 존재 여부를 빠르게 확인할 수 있습니다.
- 간선을 확인하는 시간 복잡도는 O(1)입니다.
- Dense Graph(간선이 많은 그래프)에 적합합니다.
단점
- 메모리 사용량이 많습니다.
n개의 정점이 있을 때n x n크기의 2차원 배열이 필요하므로, 간선이 적은 희소 그래프(Sparse Graph)에는 비효율적입니다.
- 모든 간선을 저장하므로, 실제 간선이 많지 않은 그래프에서는 불필요한 공간 낭비가 발생할 수 있습니다.
인접 행렬 구현 (예시: Python)
# 4개의 정점을 가진 무향 그래프를 인접 행렬로 표현
graph = [[0, 1, 1, 0], # 1번 정점과 2번, 3번이 연결
[1, 0, 0, 1], # 2번 정점과 1번, 4번이 연결
[1, 0, 0, 1], # 3번 정점과 1번, 4번이 연결
[0, 1, 1, 0]] # 4번 정점과 2번, 3번이 연결
# 간선이 있는지 확인 (1번과 2번 정점)
print(graph[0][1]) # 출력: 1 (간선 존재)인접 행렬 구현 (예시: Java)
int[][] graph = {
{0, 1, 1, 0}, // 1번 정점과 2번, 3번이 연결
{1, 0, 0, 1}, // 2번 정점과 1번, 4번이 연결
{1, 0, 0, 1}, // 3번 정점과 1번, 4번이 연결
{0, 1, 1, 0} // 4번 정점과 2번, 3번이 연결
};
// 간선이 있는지 확인 (1번과 2번 정점)
System.out.println(graph[0][1]); // 출력: 1 (간선 존재)4.2 인접 리스트 (Adjacency List)
인접 리스트는 그래프의 각 정점에 연결된 정점의 리스트를 사용하는 표현 방법입니다.
- 각 정점은 자신과 연결된 이웃 정점들의 목록을 가지고 있습니다.
- 이러한 리스트는 배열, 연결 리스트, 또는 해시테이블을 사용하여 구현할 수 있습니다.
장점
- 메모리 사용량이 효율적입니다.
- 간선만 저장하므로 Sparse Graph(간선이 적은 그래프)에 적합합니다.
- 정점에 연결된 간선들을 순회(traversal)하는 데 용이합니다.
단점
- 간선의 존재 여부를 확인하려면 연결된 리스트를 순회해야 하므로, 시간 복잡도는
O(k)(k는 해당 정점에 연결된 간선 수)입니다. - 밀집 그래프 (Dense Graph)에는 오히려 메모리 사용이 비효율적일 수 있습니다.
인접 리스트 구현 (예시: Python)
# 4개의 정점을 가진 무향 그래프를 인접 리스트로 표현
graph = {
1: [2, 3], # 1번 정점이 2번, 3번과 연결
2: [1, 4], # 2번 정점이 1번, 4번과 연결
3: [1, 4], # 3번 정점이 1번, 4번과 연결
4: [2, 3] # 4번 정점이 2번, 3번과 연결
}
# 간선이 있는지 확인 (1번 정점과 2번 정점)
print(2 in graph[1]) # 출력: True (간선 존재)
인접 리스트 구현 (예시: Java)
import java.util.ArrayList;
import java.util.HashMap;
public class Graph {
public static void main(String[] args) {
HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
graph.put(1, new ArrayList<>(List.of(2, 3))); // 1번 정점이 2번, 3번과 연결
graph.put(2, new ArrayList<>(List.of(1, 4))); // 2번 정점이 1번, 4번과 연결
graph.put(3, new ArrayList<>(List.of(1, 4))); // 3번 정점이 1번, 4번과 연결
graph.put(4, new ArrayList<>(List.of(2, 3))); // 4번 정점이 2번, 3번과 연결
// 간선이 있는지 확인 (1번 정점과 2번 정점)
System.out.println(graph.get(1).contains(2)); // 출력: true (간선 존재)
}
}4-3. 인접행렬 & 인접리스트 비교
| 표현 방법 | 장점 | 단점 | 적용 예시 |
|---|---|---|---|
| 인접 행렬 | 간선의 존재 여부를 O(1) 시간에 확인 | 메모리 사용량이 많음 | Dense Graph |
| 인접 리스트 | 메모리 효율적, Sparse Graph에 적합 | 간선의 존재 여부 확인에 O(k) 시간이 소요 | Sparse Graph |
그래프의 표현 방법은 그래프의 밀도와 크기 그리고 사용 목적에 따라 선택하는 것이 중요합니다.
- 일반적으로 Dense Graph에는 인접 행렬이 더 적합하며, Sparse Graph에는 인접 리스트가 더 효율적입니다.
다만 순회(traversal)를 하는 경우, 인접 리스트가 각 정점에 연결된 정점을 탐색하는 데 상대적으로 더 효율적입니다.
- 즉, 정점 간 연결을 빠르게 확인하는 것이 중요하다면 인접 행렬이 유리하며, 메모리 효율성이 더 중요하고 정점 주변의 간선들을 효율적으로 탐색해야 한다면 인접 리스트가 더 적합합니다.
순회와 적용 예시:
-
인접 행렬: 모든 정점에 대해 연결 여부를 빠르게 확인할 수 있으므로, 그래프의 연결성을 확인하는 경우에 유리합니다.
- 예를 들어 네트워크 흐름 알고리즘이나 플로이드-워셜 알고리즘(모든 쌍의 최단 경로)과 같은 경우에 인접 행렬이 적합합니다.
-
인접 리스트: DFS, BFS와 같은 그래프 탐색 알고리즘을 수행할 때 메모리 사용량이 적고, 인접한 노드를 빠르게 탐색할 수 있기 때문에 이 방식이 자주 사용됩니다.
- 특히, 최단 경로 탐색(예: 다익스트라 알고리즘, 벨만-포드 알고리즘)이나 트리 탐색 등에 유리합니다.
5. Graph 구현 (Java & Python)
이번 섹션에서는 대표적인 프로그래밍 언어인 Java와 Python에서 그래프를 어떻게 구현할 수 있는지 살펴보겠습니다.
- 두 언어 모두 인접 리스트(Adjacency List) 방식을 주로 사용하여 그래프를 표현합니다.
- 이 방식은 메모리를 효율적으로 사용하면서 그래프의 탐색 및 조작을 보다 쉽게 할 수 있습니다.
5-1. Graph 구현 - Java
Java에서는 주로 HashMap과 ArrayList를 사용하여 인접 리스트 방식으로 그래프를 구현합니다.
- 정점을
HashMap의 키로, 해당 정점에 연결된 다른 정점들의 리스트를 값으로 저장하는 방식입니다.
(Java) 기본적인 그래프 클래스 설계
import java.util.*;
class Graph {
private Map<String, List<String>> adjList; // 인접 리스트
// 생성자
public Graph() {
adjList = new HashMap<>();
}
// 정점 추가
public void addVertex(String vertex) {
adjList.putIfAbsent(vertex, new ArrayList<>());
}
// 간선 추가 (무향 그래프)
public void addEdge(String vertex1, String vertex2) {
adjList.get(vertex1).add(vertex2);
adjList.get(vertex2).add(vertex1);
}
// 인접 리스트 출력
public void displayGraph() {
for (String vertex : adjList.keySet()) {
System.out.print(vertex + " -> ");
System.out.println(adjList.get(vertex));
}
}
}
public class Main {
public static void main(String[] args) {
Graph graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "C");
graph.displayGraph();
}
}- 정점 추가:
addVertex(String vertex)메서드는 주어진 정점을 그래프에 추가합니다. - 간선 추가:
addEdge(String vertex1, String vertex2)메서드는 두 정점 간에 간선을 추가합니다. 무향 그래프의 경우 두 정점 모두 연결해주어야 합니다. - 그래프 출력:
displayGraph()메서드는 그래프의 인접 리스트를 출력합니다.
5-2. Graph 구현 - Python
Python에서는 주로 딕셔너리(Dictionary)를 사용하여 인접 리스트 방식으로 그래프를 구현합니다.
- 각 정점을 딕셔너리의 키로, 해당 정점에 연결된 정점들의 리스트를 값으로 저장하는 방식입니다.
(Python) 기본적인 그래프 클래스 설계
class Graph:
def __init__(self):
self.graph = {} # 인접 리스트
# 정점 추가
def add_vertex(self, vertex):
if vertex not in self.graph:
self.graph[vertex] = []
# 간선 추가 (무향 그래프)
def add_edge(self, vertex1, vertex2):
if vertex1 in self.graph and vertex2 in self.graph:
self.graph[vertex1].append(vertex2)
self.graph[vertex2].append(vertex1)
# 인접 리스트 출력
def display_graph(self):
for vertex in self.graph:
print(vertex, "->", self.graph[vertex])
# 그래프 생성 및 출력
g = Graph()
g.add_vertex("A")
g.add_vertex("B")
g.add_vertex("C")
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "C")
g.display_graph()
- 정점 추가:
add_vertex(vertex)메서드는 주어진 정점을 그래프에 추가합니다. - 간선 추가:
add_edge(vertex1, vertex2)메서드는 두 정점 간에 간선을 추가합니다. 무향 그래프의 경우 두 정점을 모두 연결해주어야 합니다. - 그래프 출력:
display_graph()메서드는 그래프의 인접 리스트를 출력합니다.
6. Graph 관련 알고리즘 소개 (탐색, 응용)
이번 섹션에서는 Graph와 관련된 주요 알고리즘들 중 탐색 알고리즘과 응용 알고리즘들에 대한 간단한 소개를 진행하겠습니다.
구체적인 알고리즘 구현과 자세한 설명은 이후의 알고리즘 시리즈에서 따로 다룰 예정입니다.
6.1 그래프 탐색 알고리즘
그래프에서의 탐색(Search)은 중요한 문제로, 대표적으로 DFS(Depth-First Search)와 BFS(Breadth-First Search)가 많이 사용됩니다.
DFS (Depth-First Search):
-
DFS는 한 정점에서 출발해 더 깊이 있는 정점으로 먼저 탐색을 진행하는 방법입니다.
- 재귀나 스택을 이용해 구현할 수 있습니다.
-
특징: 주로 모든 경로를 탐색하거나 사이클을 찾는 문제 등에 사용됩니다.
-
DFS 탐색 과정:
- 시작 정점을 방문하고, 방문된 정점들을 기록.
- 현재 정점에서 방문하지 않은 인접 정점을 찾아 재귀적으로 탐색.
- 더 이상 탐색할 정점이 없으면, 이전 정점으로 돌아갑니다.
BFS (Breadth-First Search):
-
BFS는 한 정점에서 출발해 인접한 정점들을 먼저 탐색한 후, 다음 깊이로 넘어가는 방식입니다.
- 주로 큐(Queue)를 이용해 구현됩니다.
-
특징: 최단 경로를 찾는 문제나 탐색 깊이가 얕은 경우에 주로 사용됩니다.
-
BFS 탐색 과정:
- 시작 정점을 방문하고 큐에 넣습니다.
- 큐에서 정점을 꺼내고, 해당 정점과 인접한 정점들을 큐에 넣고 탐색을 계속합니다.
- 큐가 비워질 때까지 이 과정을 반복합니다.
(Python) DFS와 BFS 간단 구현 예시
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, vertex, neighbor):
if vertex not in self.graph:
self.graph[vertex] = []
self.graph[vertex].append(neighbor)
# DFS 구현 (재귀)
def dfs(self, vertex, visited=None):
if visited is None:
visited = set()
visited.add(vertex)
print(vertex, end=' ')
for neighbor in self.graph[vertex]:
if neighbor not in visited:
self.dfs(neighbor, visited)
# BFS 구현 (큐 사용)
def bfs(self, vertex):
visited = set()
queue = [vertex]
visited.add(vertex)
while queue:
current = queue.pop(0)
print(current, end=' ')
for neighbor in self.graph[current]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
# 그래프 생성 및 탐색 예시
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'E')
print("DFS 탐색: ")
g.dfs('A') # 출력: A B D C E
print("\nBFS 탐색: ")
g.bfs('A') # 출력: A B C D E(Java) DFS와 BFS 간단 구현 예시
import java.util.*;
class Graph {
private Map<String, List<String>> adjList;
// 생성자
public Graph() {
adjList = new HashMap<>();
}
// 간선 추가
public void addEdge(String vertex, String neighbor) {
adjList.putIfAbsent(vertex, new ArrayList<>());
adjList.get(vertex).add(neighbor);
adjList.putIfAbsent(neighbor, new ArrayList<>());
adjList.get(neighbor).add(vertex); // 무향 그래프의 경우 양방향으로 간선 추가
}
// DFS 구현 (재귀)
public void dfs(String vertex, Set<String> visited) {
visited.add(vertex);
System.out.print(vertex + " ");
for (String neighbor : adjList.get(vertex)) {
if (!visited.contains(neighbor)) {
dfs(neighbor, visited);
}
}
}
// BFS 구현 (큐 사용)
public void bfs(String startVertex) {
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
visited.add(startVertex);
queue.add(startVertex);
while (!queue.isEmpty()) {
String vertex = queue.poll();
System.out.print(vertex + " ");
for (String neighbor : adjList.get(vertex)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
public static void main(String[] args) {
Graph graph = new Graph();
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "E");
System.out.println("DFS 탐색:");
graph.dfs("A", new HashSet<>()); // 출력: A B D C E
System.out.println("\nBFS 탐색:");
graph.bfs("A"); // 출력: A B C D E
}
}
6.2 그래프 응용 알고리즘
그래프는 여러 응용 문제에서 자주 사용되며, 이를 해결하기 위한 다양한 알고리즘이 존재합니다. 여기에서는 그중 일부를 간단하게 소개합니다.
최단 경로 알고리즘:
- 다익스트라 알고리즘(Dijkstra’s Algorithm):
- 가중치가 있는 그래프에서 특정 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다.
- 우선순위 큐를 사용하여 최적의 경로를 탐색합니다.
- 벨만-포드 알고리즘(Bellman-Ford Algorithm):
- 음수 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘입니다.
- 다익스트라 알고리즘과는 다르게 음수 간선도 처리할 수 있습니다.
- 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm):
- 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘입니다.
- 동적 계획법(DP)을 사용하여 그래프의 모든 경로를 탐색합니다.
최소 신장 트리(MST) 알고리즘:
- 크루스칼 알고리즘(Kruskal’s Algorithm): 최소 신장 트리를 찾는 알고리즘으로, 간선을 가중치 순으로 정렬하여 사이클을 만들지 않도록 간선을 선택하는 방식입니다.
- 프림 알고리즘(Prim’s Algorithm): 하나의 정점에서 시작해 인접한 간선들 중에서 가장 가중치가 작은 간선을 선택하면서 트리를 확장해가는 방식으로 최소 신장 트리를 구성합니다.
위상 정렬(Topological Sorting):
- 유향 비순환 그래프(DAG)에서 정점의 순서를 나열하는 알고리즘으로, 작업 순서를 정하는 문제에 자주 사용됩니다.
사이클 탐지(Cycle Detection):
- 그래프 내에서 사이클이 존재하는지 확인하는 알고리즘입니다.
- DFS 탐색을 이용해 방문된 정점에 다시 도달할 경우 사이클이 있음을 알 수 있습니다.
위의 알고리즘에 대한 구체적인 구현과 설명은 이후 알고리즘 시리즈에서 자세히 다룰 예정입니다.
마무리
이번 포스팅에서는 그래프의 다양한 표현 방법과 구현 방법을 살펴보고, 탐색 알고리즘인 DFS와 BFS에 대해서도 간단히 구현 예시를 통해 알아보았습니다. 그리고 그래프와 관련된 응용 알고리즘들에 대해서도 간략히 소개해 드렸습니다.
그래프는 다양한 실제 문제를 해결하는 데 중요한 자료구조로, 최단 경로 탐색, 네트워크 흐름 분석, 트리 구조 응용 등 광범위하게 사용됩니다. 이를 이해하고 나면, 알고리즘 문제 풀이뿐만 아니라 현실 세계의 복잡한 문제들을 해결하는 데 큰 도움이 될 것입니다.
다음 포스팅부터는 비선형 자료구조의 또 다른 큰 축인 Tree 구조에 대해 다뤄보려 합니다.
- 트리는 그래프의 한 종류이면서도 계층 구조를 기반으로 하는 특수한 구조로, 이진 트리, 이진 탐색 트리(BST), AVL 트리, 레드-블랙 트리 등을 통해 데이터의 효율적인 관리와 탐색을 가능하게 해줍니다.
일 때문에 포스팅은 잠시 쉬어요 ㅠ 바쁘다 바빠 모두들 화이팅! // Machine Learning (AI) Engineer & BackEnd Engineer (Entry)