📚 그래프

✅ 그래프란?

연결 관계를 표현하는 자료 구조.
정점이라 불리는 데이터를, 간선 혹은 링크로 연결한 형태의 자료구조를 말함
노드와 노드를 간선으로 연결한 트리도 사실 그래프의 일종
트리는, 사이클을 형성하지 않고, 연결될 노드 간에 상하 관계를 갖는 반면, 사이클을 형성할 수도 있고, 상하 관계 또한 가지지 않는다.

📌 그래프의 종류와 구현

간선이 어떠한 형태로 정점을 연결 하냐에 따라, 그래프의 종류가 달라질 수 있다.
연결/비연결 그래프
방향/무방향 그래프
가중치 그래프
서브 그래프

연결 그래프 / 비연결 그래프
임의의 두 정점 사이를 잇는 경로가 있느냐 없느냐로 나뉜다.
연결 그래프는, 아무 정점이나 골라 간선으로 서로를 이을 수 있다면 연결 그래프이다.
비연결 그래프는, 어떤 정점 사이에 경로가 존재하지 않을 수도 있다.

방향 그래프 / 무방향 그래프
간선에 방향이 있다면, 방향 그래프. 없다면 무방향 그래프

가중치 그래프
간선에 부여된 값중 가중치는 비용 이라고 불린다

서브 그래프
특정 그래프의 정점과 간선 일부분으로 이루어진 그래프

이렇게 다양한 그래프들은, 트리와 다르게 노드간 상하 관계가 없고, 같은 그래프라도 다른 모양을 띌 수 있다.
구현하는 방법에는 크게 두가지가 있다.
인접 행렬로 표현
인접 리스트로 표현

📌 인접 행렬 기반 그래프 표현

인접 행렬 기반 그래프 표현으니 N x N 크기의 행렬로 그래프를 표현하는 방법이다.
N x N 행렬에서, <행, 열> 은, <출발 정점, 도착 정점> 으로 표현하고, 들어가는 값은 연결되었을 땐 1, 연결되지 않았을 땐 0 으로 표기한다.

만약 무방향 그래프라면, 정점 1 -> 2 뿐만 아니라, 2 -> 1로도 이동이 가능하므로, 둘 다 표기를 한다

만약 가중치 방향 그래프라면, 0 or 1 대신, 가중치를 표기한다.

자바 예시

public class Main {
    public static void main(String[] args) {
        int N = 4; int[][] graph = new int[N][N]; // 간선 추가 (무방향)
        graph[0][1] = 1; graph[1][0] = 1;
        graph[0][2] = 1; graph[2][0] = 1;
        graph[1][2] = 1; graph[2][1] = 1;
        graph[2][3] = 1; graph[3][2] = 1;
        // 행렬 출력
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
    }
}

📌 인접 리스트 기반 그래프 표현

인접 리스트 기반 그래프 표현은, 그래프의 특정 정점과 연결된 정점들을 연결 리스트로 표현하는 방법

만약 가중치 그래프라면, 하나의 노드를 표현하는 정보에 가중치 정보까지 포함하면 된다.

✅ 깊이 우선 탐색과 넓이 우선 탐색

그래프의 모든 정점을 순회하는 방법은 크게 두가지가 있다
깊이 우선 탐색과 넓이 우선 탐색

📌 깊이 우선 탐색 (DFS)

깊이 우선 탐색은, 그래프에서 더 이상 방문할 정점이 없을떄까지 최대한 깊이 탐색하는 것을 반복하는 것이다.
다음과 같은 그래프에서, 다음과 같은 순서로 방문하게 된다.

a -> b -> e -> c -> f -> d
구현할 때, 다양한 방식으로 구현할 수 있는데, 배열과 스택을 사용하여 다양하게 구현할 수 있다.
배열은, 특정 정의 방문 여부를 확인하기 위해 사용되는 경우가 많다.
스택은, 방문 중, 뒤로 가기가 필요한 경우 사용할 수 있다.
방문 순서는, a정점에서 시작해, b를 방문한 뒤, b에서 e를 확인
e에서는 더 이상 갈 수 있는 곳이 없어, a정점에서 다음 c 정점 방문
b, d 정점을 차례대로 방문 후, 종료
DFS를 코드로 구현하는 방법에는, 가장 유명한게 재귀적 탐색과, stack을 사용하는 방법이 있다.
의사 코드는 다음과 같다

void dfs(int start) {
    스택.push(start);
    방문 표시(start);
    while (스택이 비어있지 않음) {
        int v = 스택.pop();
        for (각 i에 대해) {
            if (연결되어있고(i, v) && !방문함(i)) {
                스택.push(i);
                방문 표시(i);
            }
        }
    }
}

📌 너비 우선 탐색 (BFS)

너비 우선 탐색은 인접한 모든 정점들을 모두 방문한 뒤, 방문한 정점들과 연결된 모든 정점들을 방문하는 방법입니다.
즉, DFS 와 다르게, 탐색 우선순위가 다르다.

위와 동일한 그래프에서, BFS는 다음과 같은 순서로 방문하게 된다.
a -> b -> c -> d-> e -> f
구현 방법은 다양하지만 보통 dfs 와 동일하게, 배열을 통해 방문 여부를 관리한다.
또한, 큐를 사용하여 한 정점에서 방문할 수 있는 모든 정점을 쌓아둔 뒤, 다음 정점을 방문하는 방식으로 구현한다.

void bfs(int start) {
    큐.enqueue(start);
    방문 표시(start);
    while (큐가 비어있지 않음) {
        int v = 큐.dequeue();
        for (각 i에 대해) {
            if (연결되어있고(i, v) && !방문함(i)) {
                큐.enqueue(i);
                방문 표시(i);
            }
        } 
    }
}

✅ 최단 경로 알고리즘

최단 경로 알고리즘은, 한 정점에서 목적지 정점까지 이르는 가중치의 합이 최소가 되는 경로를 결정하는 알고리즘을 말합니다.
우리 일상 속에 뿌리 깊이 녹아있는 알고리즘으로, 지도 서비스에서 최단 거리를알려주는 원리로도 사용됩니다.
네트워크에서 도 최단 경로로, 여러 네트워크 장비들을 통과하여 빠르게 수신지로 가기위해 이와같은 알고리즘을 사용하게 된다.
최단 경로 알고리즘은 정말 다양하게 있고, 대표적으로 다익스트라 알고리즘이 있다.
벨만 포드, 플로이드-워셜 또한 대표적인 최단 경로 알고리즘 이다.

📌 다익스트라

다익스트라는, 전체적인 작동 과정은 다음 절차를 따릅니다.

1️⃣ 최단 거리 테이블 상에서 시작 정점을 제외한 정점들을 모두 충분히 큰 수로 초기화 합니다.

2️⃣ (시작)정점을 방문합니다.

3️⃣방문한 정점과 인접한 정점들을 탐색합니다.

4️⃣경로 상의 가중치 합과 최단 거리 테이블 상의 값을 비교합니다.

5️⃣최단 거리 테이블을 갱신할 수 있다면 갱신합니다.

6️⃣방문하지 않은 정점 중 최단 거리가 가장 작은 정점을 방문합니다.

7️⃣더이상 방문할 정점이 없을 때 까지

3️⃣ ~ 6️⃣의 과정을 반복하고, 종료합니다.

다음은 간단한 가중치 방향 그래프를 통해 최단 거리를 구하는 과정을 예시로 설명합니다.

STEP1) 1️⃣ 과정
1️⃣최단 거리 테이블을 다음과 같이 초기화 합니다. [∞, ∞, ∞, ∞, ∞, ∞]
단, 시작 정점의 값 (0번 인덱스)의 값만 0으로 초기화 합니다. [0, ∞, ∞, ∞, ∞, ∞]

STEP2) 2️⃣ 과정
시작 정점인 1을 방문합니다.

STEP3) 3️⃣ 과정
정점1 과 인접한 정점은 정점2 입니다.

STEP4) 4️⃣ 과정
경로 상의 가중치 합과, 최단 거리 테이블 상의 값을 비교합니다.
현재, 정점2에 이르는 최단 거리 테이블에는 ∞가 저장되어있고, 1->2 로 이동하는 값은 2입니다.

STEP5) 5️⃣ 과정
2번 정점의 현재 최단 거리 테이블의 값이 ∞로, 2보다 더 크므로, 2로 갱신 해줍니다.
[0, 2, ∞, ∞, ∞, ∞]
❗ 아직 정점 2는 방문하지 않은 상태입니다. 계산만 한 상태

STEP6) 6️⃣ 과정
드디어 방문하지 않은 정점 중, 가장 최단거리(가중치)가 작은 정점을 방문합니다.
정점 2를 방문합니다.

STEP7) 7️⃣ 과정
이제 더 이상 방문할 정점이 없을 떄까지 3️⃣ ~ 6️⃣의 작업을 반복해줍니다.
기존 STEP3 부터 정점1을 기준으로 찾았다면 이제는 정점2에서 3️⃣ ~ 6️⃣의 과정을 반복해줍니다.

STEP8) 3️⃣ 과정
정점2와 인접한 정점들은 정점3, 정점4, 정점5 입니다.

STEP9) 4️⃣, 5️⃣ 과정
정점 3, 4, 5에 이르는 가중치 합과 최단 거리 테이블 상의 값을 비교합니다.
정점1 -> 정점3 은, 가중치 2 + 10
정점1 -> 정점4 는, 가중치 2 + 2
정점1 -> 정점5 는, 가중치 2 + 5
현재, 최단 거리 테이블은 모두 ∞ 이기 때문에, 비교하고 갱신해 줍니다.
[0, 2, 12, 4, 7, ∞]

STEP10) 6️⃣ 과정
방문하지 않은 정점 중 최단 거리가 가장 작은 정점을 방문합니다.
현재 위치는 2번 정점이고, 방문하지 않은 정점 중 가장 최단거리의 정점은 4번 정점 입니다.

STEP11)
4번 정점을 방문합니다.
현재 까지의 최단 거리 테이블: [0, 2, 12, 4, 7, ∞]
4번과 인접한 정점은 5번입니다.
4 → 5로 가는 가중치는 10입니다.
정점1 → 정점2 → 정점4 → 정점5로 가는 총 거리는
2(1→2) + 2(2→4) + 10(4→5) = 14
현재 최단 거리 테이블에서 5번까지는 7로 저장되어 있으므로
14 > 7 이므로 갱신하지 않습니다.

STEP12)
방문하지 않은 정점 중, 최단거리가 가장 작은 정점(5번)을 방문합니다.
5번 정점과 인접한 정점은 3번, 6번입니다.
5 → 3: 가중치 2 > 5 → 6: 가중치 3
1 → 2 → 5 → 3
2(1→2) + 5(2→5) + 2(5→3) = 9
현재 3번까지는 12로 되어 있으니, 9로 갱신
1 → 2 → 5 → 6
2(1→2) + 5(2→5) + 3(5→6) = 10
현재 6번까지는 ∞이니, 10으로 갱신
최단 거리 테이블 : [0, 2, 9, 4, 7, 10]

STEP13)
방문하지 않은 정점 중, 최단거리가 가장 작은 정점(3번)을 방문합니다.
3번 정점과 인접한 정점은 6번입니다.
3 → 6: 가중치 2
1 → 2 → 5 → 3 → 6 > 2(1→2) + 5(2→5) + 2(5→3) + 2(3→6) = 11
이미 6번까지는 10이 있으므로, 11
10이므로 갱신하지 않음

STEP14)
마지막으로, 방문하지 않은 정점 중 최단거리가 가장 작은 정점(6번)을 방문합니다.
6번 정점과 인접한 정점은 없음.
더 이상 방문할 정점이 없습니다.

### 📌 다익스트라 자바 코드

- ArrayList 와, PQ(가중치 기준 최소힙) 으로 구현된다.

- 중간에, 비교하여, 최단 거리 테이블에 최소값을 밀어넣는 과정에서, prev 배열에 기록을 하여 경로를 알아 낼 수 있도록 한다.

import java.util .*;

public class DijkstraWithPath {
	public static void main(String[] args) {
		int N = 6;
		int INF = Integer.MAX_VALUE;
		List[] graph = new ArrayList[N];
		for (int i = 0; i < N; i++)
			graph[i] = new ArrayList<>(); // 예시 그래프 (1-indexed → 0-indexed 변환 필요)
		graph[0].add(new Edge(1, 2));
		graph[1].add(new Edge(2, 10));
		graph[1].add(new Edge(3, 2));
		graph[1].add(new Edge(4, 5));
		graph[3].add(new Edge(4, 10));
		graph[4].add(new Edge(2, 2));
		graph[4].add(new Edge(5, 3));
		graph[2].add(new Edge(5, 2)); // 3->6
		int[] dist = new int[N];
		int[] prev = new int[N];
		Arrays.fill(dist, INF);
		Arrays.fill(prev, -1);
		dist[0] = 0;
		PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.cost));
		pq.offer(new Node(0, 0));
		boolean[] visited = new boolean[N];
		while (!pq.isEmpty()) {
			Node curr = pq.poll();
			int v = curr.vertex;
			if (visited[v])
				continue;
			visited[v] = true;
			for (Edge e : graph[v]) {
				if (!visited[e.to] && dist[e.to] > dist[v] + e.cost) {
					dist[e.to] = dist[v] + e.cost;
					prev[e.to] = v;
					pq.offer(new Node(e.to, dist[e.to]));
				}
			}
		} // 결과 출력 및 경로 복원 예시 (1번 → 6번)
		int target = 5; // 0-indexed, 6번 정점
		if (dist[target] == INF) {
			System.out.println("6번 정점 도달 불가");
		} else {
			System.out.println("1번부터 6번까지 최단 거리: " + dist[target]);
			List path = new ArrayList<>();
			for (int at = target; at != -1; at = prev[at]) {
				path.add(at + 1); // 1-indexed 출력
			}
			Collections.reverse(path);
			System.out.println("경로: " + path);
		}
	}

	static class Edge {
		int to, cost;

		Edge(int to, int cost) {
			this.to = to;
			this.cost = cost;
		}
	}

	static class Node {
		int vertex, cost;

		Node(int vertex, int cost) {
			this.vertex = vertex;
			this.cost = cost;
		}
	}
}

📄 참고하면 좋은 영상

📄 출처

- https://wpioneer.tistory.com/m/127

- https://jackpot53.tistory.com/86

- https://goldenrabbit.co.kr/

그래프 자료구조 학습(그래프와, 탐색, 다익스트라)