그래프📈 (Graph)

❓공부하게 된 계기

➡️ 다음 알고리즘 스터디 주제인 Graph 에 대해서 예습

❗️공부한 내용

1️⃣ 그래프란?

① 정의

➡️ 정점 (Vertex) 와 그 사이를 잇는 간선 (Edge) 로 이루어진 자료구조.

✔️ 정의
G = (V,E) : 정점의 집합 V 와 간선의 집합 E 로 이루어진 구조를 의미
V(G) : 그래프 G 안에서의 정점의 집합
E(G) : 그래프 G 안에서의 간선의 집합

② 예시 (무방향 그래프 기준)

그래프 예시

➡️ V(G) = {1, 2, 3, 4, 5}

➡️ E(G) = {(1, 2), (3, 1), (3, 2), (4, 1), (5, 2), (5, 4)}

2️⃣ 그래프 종류

① 무방향 그래프 (Undirected Graph)

➡️ 간선에 방향의 속성이 없는 그래프이다. 두 정점 V, W 를 잇는 간선을 (V, W) 라고 할 때, (V, W) == (W, V) 이다.

Undirected Graph

② 방향 그래프 (Directed Graph)

➡️ 간선에 방향의 속성이 있는 그래프이다. 두 정점 V, W 를 잇는 간선을 (V, W) 라고 할때, (V, W) != (W, V) 이다.

Directed Graph

③ 완전 그래프 (Complete Graph)

➡️ 한 정점에서 다른 정점 모두와 연결되어있는 그래프이다.

Complete Graph

④ 가중치 그래프 (Weighted Graph)

➡️ 간선 마다 가중치가 부여되어있는 그래프이다.

Weighted Graph

3️⃣ 그래프 구현 (Java) (1️⃣ 의 무방향 그래프 예시 기준)

① 인접 행렬

➡️ 서로의 연결 여부를 기록한 boolean 타입 2차원 배열 생성 (연결 : 1 / 비연결 : 0)

➡️ 무조건 n * n 의 형태 이므로 무조건 O(n²) 의 공간복잡도를 가짐

// 인접 행렬 선언
int[][] matrix = new int[n + 1][n + 1];

// 배열에 담는 과정
for(int[] edge : edges) {
    matrix[edge[0]][edge[1]] = 1;
    matrix[edge[1]][edge[0]] = 1;
}

인접 배열 형태

② 인접 리스트

➡️ 각 노드별로 연결된 노드를 배열형태로 담은 리스트를 생성

➡️ 필요한만큼만 추가되는 방식이기 때문에 상황에 따라 공간복잡도 낭비가 덜해짐

// 인접 리스트 선언 (1) : 배열 + 리스트
// ➡️ 리스트를 담고있는 배열을 선언하는 방식 (정적)
ArrayList<Integer>[] list = new ArrayList[n + 1]; // 배열 생성
for (int i = 0; i <= n; i++) list[i] = new ArrayList<>(); // 배열 안 리스트 생성

// 인접 리스트 선언 (2) : 리스트 + 리스트
// ➡️ 리스트를 담고있는 리스트를 선언하는 방식 (동적)
ArrayList<ArrayList<Integer>> list = new ArrayList<>(); // 리스트 생성
for(int i = 0 ; i <= n ; i++) list.add(new ArrayList<>()); // 리스트 안 리스트 생성

// 리스트에 담는 과정 : 배열 + 리스트
for(int[] edge : edges) {
    list[edge[0]].add(edge[1]);
    list[edge[1]].add(edge[0]);
}

// 리스트에 담는 과정 : 리스트 + 리스트
for(int[] edge : edges) {
    list.get(edge[0]).add(edge[1]);
    list.get(edge[1]).add(edge[0]);
}

인접 리스트 형태

4️⃣ 그래프 순회

① DFS & BFS

➡️ DFS 와 BFS 를 통해 그래프를 순회 (이전에 관련 내용을 정리한 글이 있으므로 링크로 대체한다.)

(Java) 깊이 우선 탐색 (DFS) & 너비 우선 탐색 (BFS )

② 다익스트라 알고리즘 + 밸먼-포드 + 사이클

➡️ 그래프 종류 중 가중치 그래프 (Weighted Graph) 의 경우 음의 가중치가 없다는 전제하에 다익스트라 알고리즘을 주로 사용한다고 한다. 해당 내용은 따로 정리해 볼 예정이다.

✏️ 적용 시켜본 예제

프로그래머스

🧐 추가로 궁금한 점