그래프 학습 동기
그래프를 왜 배울까요? 자료구조의 분류부터 차근차근 살펴보겠습니다.
자료구조는 크게 선형 자료구조와 비선형 자료구조로 나뉩니다. 그래프는 비선형 자료구조로 데이터들 간의 관계를 효율적으로 표현하는데에 있습니다.
비선형 자료구조에는 트리와 그래프가 있습니다. 트리는 부모-자식 노드간의 계층적 관계를 나타내는 반면, 그래프는 모든 노드가 서로 자유롭게 연결될 수 있습니다. 예를 들어, SNS에서 친구 관계나 지하철 노선도처럼 "누구나 누구와든 연결될 수 있는" 관계를 표현할 때 그래프가 필요합니다.
즉, 그래프를 배우는 이유는:
- 복잡한 관계를 가진 데이터를 효율적으로 표현하기 위해
- 계층적이지 않은 자유로운 연결 관계를 모델링하기 위해
그래프 기본 개념
- 정점(Vertex): 트리의 노드(Node)와 같이 한 데이터를 나타냅니다. 예를 들어, 지하철 노선도에서는 역이 정점이 됩니다.
- 간선(Edge): 정점끼리 연결된 관계를 나타냅니다.
그래프 표현 방법
인접 행렬(Adjacency Matrix)
정점(Vertex)들간의 관계를 행렬로 표현한 것입니다.
기본 구조
먼저 인접 행렬을 사용한 그래프의 기본 구조를 살펴보겠습니다:
public class AdjacencyMatrixGraph<T> {
private T[] vertices; // 정점 데이터 저장
private int[][] matrix; // 인접 행렬
private int size; // 현재 정점 개수
private int maxSize; // 최대 정점 개수
}인접 행렬 그래프는 정점들을 배열에 저장하고, 간선 연결 정보를 2차원 행렬에 저장합니다. 이제 각 메서드의 구현과 동작 방식을 자세히 살펴보겠습니다.
1. 생성자
@SuppressWarnings("unchecked")
public AdjacencyMatrixGraph(int maxSize) {
this.maxSize = maxSize;
this.vertices = (T[]) new Object[maxSize];
matrix = new int[maxSize][maxSize];
}생성자는 그래프의 초기화를 담당하며, 다음과 같은 작업을 수행합니다.
- 최대 크기 설정:
maxSize매개변수를 통해 그래프가 담을 수 있는 최대 정점 수를 지정합니다. - 메모리 할당: 두 가지 주요 데이터 구조에 메모리를 할당합니다:
vertices: 정점 객체들을 저장할 배열matrix: 간선 연결 정보를 저장할 2차원 배열
- 제네릭 배열 생성: Java에서는 제네릭 타입의 배열을 직접 생성할 수 없습니다(
new T[maxSize]와 같은 코드는 불가능). 이러한 제약을 우회하기 위해 Object 배열을 생성한 후 타입 캐스팅을 사용합니다. @SuppressWarnings("unchecked")어노테이션: 제네릭 배열 생성 시 발생하는 타입 안전성 경고를 억제합니다. 이 경고는 런타임에 실제 타입 정보가 소거되기 때문에 발생하지만, 코드 내에서 타입 안전성을 유지하도록 설계되었다면 이 경고를 무시해도 안전합니다.
제네릭 배열 생성의 한계와 해결책
Java에서 제네릭 배열을 직접 생성할 수 없는 이유는 타입 소거(type erasure) 때문입니다. 컴파일 시 제네릭 타입 정보는 소거되어 런타임에는 존재하지 않습니다. 이를 해결하기 위한 일반적인 방법은:
- Object[] 배열을 생성
- 해당 배열을 원하는 제네릭 타입으로 캐스팅
- 클래스 내부에서 타입 안전성 유지
이 방식은 컴파일러 경고를 발생시키지만, 클래스 구현이 타입 안전성을 보장한다면 실제 문제는 발생하지 않습니다.
2. addVertex 메서드
@Override
public void addVertex(T vertex) {
vertices[size++] = vertex;
}addVertex 메서드는 그래프에 새로운 정점을 추가합니다:
- 정점 추가 과정: 매개변수로 받은 정점 객체를
vertices배열의 현재size위치에 저장합니다. - 인덱스 관리:
size변수는 현재 그래프에 포함된 정점의 수를 나타내며, 후위 증가 연산자(size++)를 사용하여 정점 추가 후 자동으로 증가합니다. - 시간 복잡도: O(1) - 배열의 특정 위치에 값을 저장하는 단순 연산이므로 상수 시간이 소요됩니다.
실제 사용 예시
AdjacencyMatrixGraph<String> graph = new AdjacencyMatrixGraph<>(5);
graph.addVertex("A"); // vertices[0] = "A", size = 1
graph.addVertex("B"); // vertices[1] = "B", size = 2
graph.addVertex("C"); // vertices[2] = "C", size = 3위 코드 실행 후 vertices 배열은 ["A", "B", "C", null, null]과 같은 상태가 되며, size는 3이 됩니다.
주의사항
현재 구현에는 다음과 같은 제한사항이 있습니다:
- 정점이 이미 존재하는지 확인하지 않습니다.
- 배열 용량 초과 검사가 없습니다(size >= maxSize).
- 중복 정점 검사 로직이 없습니다.
실제 프로덕션 코드에서는 이러한 예외 상황을 처리하는 코드를 추가하는 것이 좋습니다.
3. addEdge 메서드
@Override
public void addEdge(int from, int to) {
if (from < 0 || from >= size || to < 0 || to >= size) {
throw new IllegalArgumentException("Invalid vertex index");
}
matrix[from][to] = 1;
matrix[to][from] = 1;
}addEdge 메서드는 두 정점 사이에 간선을 추가합니다:
- 경계 검사(Boundary Check): 매개변수로 받은 정점 인덱스가 유효한 범위인지 확인합니다. 유효하지 않은 인덱스(음수이거나 size 이상)가 주어지면 예외를 발생시켜 프로그램 오류를 방지합니다.
- 간선 추가: 인접 행렬의 해당 위치에 1을 설정하여 간선의 존재를 표시합니다.
matrix[from][to] = 1: from에서 to로 가는 간선 추가matrix[to][from] = 1: to에서 from으로 가는 간선 추가 (무방향 그래프의 경우)
- 무방향/방향 그래프 처리 차이:
- 무방향 그래프: 양방향 모두 설정 (
matrix[from][to]와matrix[to][from]모두 1로 설정) - 방향 그래프: 단방향만 설정 (
matrix[from][to]만 1로 설정,matrix[to][from]은 설정하지 않음)
- 시간 복잡도: O(1) - 배열의 특정 위치에 값을 설정하는 단순 연산이므로 상수 시간이 소요됩니다.
실제 사용 예시
AdjacencyMatrixGraph<String> graph = new AdjacencyMatrixGraph<>(5);
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge(0, 1); // "A"와 "B" 연결
graph.addEdge(0, 2); // "A"와 "C" 연결위 코드 실행 후 인접 행렬 matrix는 다음과 같은 상태가 됩니다:
[ [0, 1, 1],
[1, 0, 0],
[1, 0, 0] ]이는 "A"가 "B"와 "C"에 연결되어 있음을 나타냅니다.
4. DFS (Depth First Search)
- 재귀를 이용한 DFS
public void depthFirstSearch() {
resetVisited(); // 방문 초기화
for (int i = 0; i < size; i++) {
if (!visited[i])
depthFirstSearch(i);
}
System.out.println();
}
private void depthFirstSearch(int v) {
visited[v] = true;
System.out.print(vertices[v] + " ");
for (int w = 0; w < maxSize; w++) {
if (matrix[v][w] == 1 && !visited[w]) {
depthFirstSearch(w);
}
}
}- 설명: 가장 직관적인 DFS 구현. 함수 호출 스택을 이용해 자연스럽게 깊이 우선 탐색을 수행합니다.
- 출력:
A B D G E F C
- Stack 기반 DFS (첫 번째 시도)
public void iterativeDFSBadVersion() {
resetVisited();
int v = 0;
Stack<Integer> s = new ArrayStack<>(maxSize);
visited[v] = true; // 스택에서 pop하기 전에 방문 표시
s.push(v);
while (!s.isEmpty()) {
v = s.peek();
s.pop();
System.out.print(vertices[v] + " ");
for (int w = 0; w < maxSize; w++) {
if (matrix[v][w] == 1 && !visited[w]) {
visited[w] = true; // 스택에 넣을 때 방문 표시
s.push(w);
}
}
}
System.out.println();
}- 문제점: A에서 B를 "선택"했지만(스택에 넣음), B를 완료하지 않고 C를 먼저 처리합니다. 이는 "깊이 우선"이 아닌 "스택 순서 우선" 탐색이 됩니다.
- A→B→D→G 경로를 완료해야 하는데, A→C→E→G→D→B 순서로 탐색됩니다.
- 출력:
A C E G F D B(재귀 DFS와 다른 순서)
- Stack 기반 DFS (올바른 구현)
public void iterativeDFSV2() {
resetVisited();
int v = 0;
Stack<Integer> s = new ArrayStack<>(maxSize);
s.push(v);
while (!s.isEmpty()) {
v = s.peek();
s.pop();
if (visited[v]) {
continue;
}
visited[v] = true; // 꺼낼 때 방문 표시
System.out.print(vertices[v] + " ");
for (int w = size - 1; w >= 0; w--) {
if (matrix[v][w] == 1 && !visited[w]) {
s.push(w);
}
}
}
System.out.println();
}- 개선점: 스택에서 꺼낼 때 방문 체크하여 올바른 DFS를 구현합니다.
- 출력:
A B D G E F C(재귀 DFS와 유사한 순서)
- Iterator 기반 DFS (재귀와 동일한 순서)
위의 스택 기반 구현들은 모두 한계가 있습니다:
- 첫 번째 시도: 직관적이지만 잘못된 탐색 순서
- 올바른 구현: 정확한 DFS이지만 "꺼낼 때 방문 체크"라는 비직관적 방식 사용
Iterator를 사용하는 이유:
재귀 DFS의 핵심은 "현재 위치에서 다음 선택을 바로 처리"하는 것입니다. Iterator는 각 정점에서 "어디까지 탐색했는지" 정확히 기억하므로, 재귀와 동일한 방식으로 동작할 수 있습니다.
- 큐: 이전에 보관된 정점들을 순서대로 처리 → BFS가 됨
- 일반 스택: 선택 순서와 처리 순서가 반대 → 비직관적
- Iterator: 현재 위치에서 다음 선택을 바로 처리 → 재귀와 동일
public void iterativeDFSWithIterator() {
resetVisited();
Stack<Iterator<Integer>> s = new ArrayStack<>(maxSize);
int start = 0;
visited[start] = true;
System.out.print(vertices[start] + " ");
s.push(getAdjacencyIterator(start));
while (!s.isEmpty()) {
Iterator<Integer> current = s.peek();
if (current.hasNext()) {
int w = current.next(); // 현재 위치에서 다음 선택
if (!visited[w]) {
visited[w] = true;
System.out.print(vertices[w] + " ");
s.push(getAdjacencyIterator(w)); // 새 위치로 이동
}
} else {
s.pop(); // 현재 위치에서 더 갈 곳이 없으면 이전 위치로 백트래킹
}
}
}- 특징: 재귀 DFS와 정확히 동일한 방문 순서를 보장합니다.
- 출력:
A B D G E F C(재귀 DFS와 완전히 동일)
5. BFS (Breadth First Search)
큐를 사용하여 너비 우선 탐색을 수행합니다. 시작 정점에서 가까운 정점들부터 차례로 방문합니다.
public void breadthFirstSearch() {
resetVisited(); // 방문 초기화
// 학습용이므로 간단히 LinkedList로 구현
Queue<Integer> queue = new LinkedList<>();
int start = 0;
visited[start] = true; // 삽입하기 전에 방문 표시
queue.offer(start);
System.out.print(vertices[start] + " ");
while (!queue.isEmpty()) {
int v = queue.poll();
for (int w = 0; w < size; w++) {
if (!visited[w] && matrix[v][w] == 1) {
visited[w] = true;
queue.offer(w);
System.out.print(vertices[w] + " ");
}
}
}
System.out.println();
}- 출력:
A B C D E G F(레벨별 탐색 순서)
인접 리스트(Adjacency List)
정점(Vertex)들간의 관계를 연결 리스트로 표현한 것입니다. 인접 행렬과 달리 각 정점마다 실제로 연결된 정점들만 저장하여 메모리를 효율적으로 사용합니다.
먼저 인접 리스트를 사용한 그래프의 기본 구조를 살펴보겠습니다:
public class AdjacencyListGraph<T> implements Graph<T> {
private T[] vertices; // 정점 데이터 저장
private Node[] list; // 각 정점의 인접 리스트 헤드 배열
private int size; // 현재 정점 개수
private int maxSize; // 최대 정점 개수
private boolean[] visited; // DFS/BFS용 방문 체크 배열
}인접 리스트 그래프는 정점들을 배열에 저장하고, 각 정점의 연결 정보를 개별 연결 리스트에 저장합니다. 이제 각 메서드의 구현과 동작 방식을 자세히 살펴보겠습니다.
Node 클래스
연결 리스트를 구현하기 위한 노드 클래스입니다:
static class Node {
int vertex = -1; // 연결된 정점의 인덱스
Node next = null; // 다음 노드 참조
public Node(int vertex, Node next) {
this.vertex = vertex;
this.next = next;
}
}설계 특징:
- 정점 인덱스 저장: 연결된 정점의 배열 인덱스를 저장합니다
- 단일 연결 구조: 다음 노드만 참조하는 단순한 구조로 메모리 효율성을 높입니다
- 생성자 편의성: 노드 생성과 동시에 값 설정이 가능합니다
1. 생성자
@SuppressWarnings("unchecked")
public AdjacencyListGraph(int maxSize) {
this.maxSize = maxSize;
this.vertices = (T[]) new Object[maxSize];
list = new Node[maxSize];
}생성자는 그래프의 초기화를 담당하며, 다음과 같은 작업을 수행합니다:
- 최대 크기 설정:
maxSize매개변수를 통해 그래프가 담을 수 있는 최대 정점 수를 지정합니다 - 메모리 할당: 세 가지 주요 데이터 구조에 메모리를 할당합니다:
vertices: 정점 객체들을 저장할 배열list: 각 정점의 인접 리스트 헤드를 저장할 배열
- 제네릭 배열 생성: 인접 행렬과 동일한 방식으로 Object 배열을 생성 후 타입 캐스팅을 사용합니다
인접 행렬과의 차이점:
- 인접 행렬:
O(V^2)크기의 2차원 배열 할당 - 인접 리스트:
O(V)크기의 1차원 배열만 할당 (연결 리스트는 필요시 동적 생성)
2. addVertex 메서드
@Override
public void addVertex(T vertex) {
vertices[size++] = vertex;
}addVertex 메서드는 인접 행렬과 동일한 방식으로 구현됩니다:
- 정점 추가: 매개변수로 받은 정점 객체를
vertices배열의 현재 size 위치에 저장 - 인덱스 관리: 후위 증가 연산자로 정점 추가 후 자동 증가
- 시간 복잡도: O(1) - 배열 접근은 상수 시간
주목할 점: 이 시점에서는 list[size-1]이 여전히 null입니다. 간선이 추가될 때까지 연결 리스트가 생성되지 않습니다.
3. addEdge 메서드
@Override
public void addEdge(int from, int to) {
if (from < 0 || from >= size || to < 0 || to >= size) {
throw new IllegalArgumentException(
"Invalid vertex index");
}
Node temp = new Node(to, list[from]);
list[from] = temp;
}addEdge 메서드는 Head Insertion 방식으로 간선을 추가합니다:
- 경계 검사: 인접 행렬과 동일한 유효성 검사를 수행합니다
- 새 노드 생성:
new Node(to, list[from])
vertex = to: 연결될 정점 번호 설정next = list[from]: 기존 리스트를 다음 노드로 연결
- 헤드 교체:
list[from] = temp로 새 노드를 리스트의 맨 앞에 배치 - 시간 복잡도:
O(1)- 리스트 맨 앞 삽입은 상수 시간
4. Head Insertion의 특징
Head Insertion은 연결 리스트의 맨 앞에 새 노드를 삽입하는 방식입니다:
// 초기 상태: list[0] → null
addEdge(0, 1); // list[0] → [1|next:null]
addEdge(0, 2); // list[0] → [2|next:→[1|next:null]]
addEdge(0, 3); // list[0] → [3|next:→[2|next:→[1|next:null]]]5. DFS (Depth First Search)
- 재귀 기반 DFS
public void depthFirstSearch() {
resetVisited();
depthFirstSearch(0);
System.out.println();
}
private void depthFirstSearch(int v) {
visited[v] = true;
System.out.print(vertices[v] + " ");
Node current = list[v];
while (current != null) {
int w = current.vertex;
if (!visited[w]) {
depthFirstSearch(w);
}
current = current.next;
}
}// 인접 행렬 방식
for (int w = 0; w < maxSize; w++) {
if (matrix[v][w] == 1 && !visited[w]) {
depthFirstSearch(w);
}
}
// 인접 리스트 방식
Node current = list[v];
while (current != null) {
int w = current.vertex;
if (!visited[w]) {
depthFirstSearch(w);
}
current = current.next;
}시간 복잡도: O(V + E)
- 각 정점을 한 번씩 방문: O(V)
- 각 간선을 한 번씩 확인: O(E)
- 반복적 DFS (Stack 기반)
public void iterativeDFS() {
resetVisited();
int start = 0;
Stack<Integer> s = new ArrayStack<>(maxSize);
s.push(start);
while (!s.isEmpty()) {
int v = s.peek();
s.pop();
if (visited[v]) {
continue; // 이미 방문한 정점은 건너뛰기
}
visited[v] = true;
System.out.print(vertices[v] + " ");
Node current = list[v];
while (current != null) {
int w = current.vertex;
if (!visited[w]) {
s.push(w);
}
current = current.next;
}
}
System.out.println();
}6. BFS (Breadth First Search) 구현
public void breadthFirstSearch() {
resetVisited();
Queue<Integer> q = new LinkedList<>();
int start = 0;
visited[start] = true;
q.offer(start);
System.out.print(vertices[start] + " ");
while (!q.isEmpty()) {
int v = q.poll(); // Vertex 수만큼 확인
Node current = list[v];
while (current != null) {
int w = current.vertex; // 간선 확인
if (!visited[w]) {
visited[w] = true;
System.out.print(vertices[w] + " ");
q.offer(w);
}
current = current.next;
}
}
System.out.println();
}인접 행렬과 비교
인접 행렬 BFS:
for (int w = 0; w < size; w++) {
if (!visited[w] && matrix[v][w] == 1) {
// ...
}
}각 정점마다 모든 정점(V개) 확인
시간 복잡도: O(V²)
인접 리스트 BFS:
Node current = list[v];
while (current != null) {
// 실제 연결된 정점들만 확인
current = current.next;
}각 정점마다 실제 연결된 정점들만 확인
시간 복잡도: O(V + E)
- O(V): 각 정점을 정확히 한 번씩 큐에서 처리
- O(E): 모든 간선을 정확히 한 번씩 확인 (각 정점에서 나가는 간선들의 합 = E), 실제로는 2E지만 상수 배수 제외.
