✔ 목차
- 그래프란?
- 그래프 용어
- 그래프 종류
- 그래프 구현 - Java
- 그래프 순회
- 최소 신장 트리
- 최단 경로
🔎 그래프란?
그래프는 정점(Vertex)과 그 사이를 잇는 간선(Edge)로 이루어진다.
G = (V, E)는 정점의 집합 V와 간선의 집합 E라고 할 때, 그래프 G는 V와 E의 집합 (V, E)라는 뜻이다.
V(G)는 그래프 G의 정점 집합이고, E(G)는 그래프 G의 간선 집합이다. 간선은 (정점 v, 정점 w)형식이다.
예시)
V(G) = {1, 2, 3, 4, 5}
E(G) = {(1, 2), (3, 1), (3, 2), (4, 1), (5, 2), (5, 4)}
추가) 트리도 그래프의 한 종류이다.
🔎 그래프 용어
정점(Vertex): 노드(node), 데이터 저장간선(Edge): 정점을 연결하는 선분지수(차수, degree): 무방향 그래프에서 하나의 정점에 붙어있는 간선 개수내향 분지수(진출 차수, in-degree): 방향 그래프에서 들어오는 간선의 수외향 분지수(진입 차수, out-degree): 방향 그래프에서 나가는 간선의 수- 인접
인접(adjacent): 정점 사이 간선이 있음부속(incident): 정점과 간선 사이 관계
경로(path): 출발지에서 목적지로 가는 순서단순 경로(simple path): 경로 중 반복되는 정점이 없음, 한붓그리기처럼 같은 간선 지나지 않음사이클(cycle): 단순 경로의 출발지와 목적지가 같은 경우
🔎 그래프 종류
여기서는 그래프의 종류 중 대표적으로 무방향, 방향, 완전, 가중치 그래프 4가지를 소개한다. 이 4가지 이외에도 다중 그래프, 다중 에지 등 다양하게 그래프는 존재한다.
무방향 그래프(Undirected Graph)
간선에 방향이 없는 그래프이다. 정점 v와 정점 w를 연결하는 간선을 (v, w)라고 하면, (v, w)와 (w, v)는 같은 간선이다.
정점 n개일 때 무방향 그래프가 가질 수 있는 최대 간선 수는 n(n-1)/2개 이다.
방향 그래프(Directed Graph)
간선에 방향이 있는 그래프이다. 정점 v에서 w로 가는 간선을 (v, w)라고 하고, 이때는 간선 (w, v)와 다르다.
정점 n개일 때 방향 그래프가 가질 수 있는 최대 간선 수는 n(n-1)개 이다.
완전 그래프(Complete graph)
모든 정점에 간선이 있고, 한 정점에서 다른 정점과 모두 연결되어 있다.
가중치 그래프(Weighted graph)
간선에 가중치(=비용)가 있다.
💻 그래프 구현 - Java
그래프는 인접행렬 또는 인접리스트로 표현할 수 있다.
1. 그래프 구현 - 인접행렬
- 2차원 배열 matrix 사용
matrix[v][w] = 1: 정점 v에서 정점 w로 가는 간선이 있음matrix[v][w] = 0: 정점 v에서 정점 w로 가는 간선이 없음- 예시) 정점 5는 정점 2와 정점 4와 연결되어있음, 위의 행렬이 matrix라고 하면 matrix[5][2] = 1, matrix[5][4] =1 이고 나머지는 0
- 장점
- 연결된 정점 찾기 빠름
- 구현 쉬움
- 단점
O(n^2)의 공간복잡도 가짐
구현 코드
public static void main(String[] args) {
int[][] edges = new int[][] {
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
};
int n = 5; //정점의 개수
int[][] matrix = new int[n + 1][n + 1];
for(int[] edge : edges) {
matrix[edge[0]][edge[1]] = 1;
matrix[edge[1]][edge[0]] = 1;
}
//출력
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= n ; j++) {
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
}출력 결과
0 1 1 1 0 0
1 0 1 0 1 0
1 1 0 0 0 0
1 0 0 0 1 0
0 1 0 1 0 0 2. 그래프 구현 - 인접 리스트
- 배열 또는 리스트 사용
- 정점의 개수만큼 헤드 노드가 있고, 각 정점에 인접한 정점들 리스트로 연결
- 정점 v의 인접 정점이 w와 z라면 헤드노드 v에 w와 z가 연결 리스트로 연결되어있음
- 예시) 정점 5는 정점 2와 정점 4와 연결되어있음, 5번 인덱스에 2와 4가 리스트로 연결
- 장점
- 필요한 만큼 공간 사용하기 때문에 공간 낭비 적음
- 단점
- 인접 행렬보다 구현 어려움
- 인접 행렬보다 구현 어려움
구현 코드 - 1. 배열 + 리스트
public static void main(String[] args) {
int[][] edges = new int[][] {
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
};
int n = 5;
ArrayList<Integer>[] list = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) list[i] = new ArrayList<>();
for(int[] edge : edges) {
list[edge[0]].add(edge[1]);
list[edge[1]].add(edge[0]);
}
//출력
for (int i = 1; i <= n; i++) {
for(int j = 0 ; j < list[i].size();j++)
System.out.print(list[i].get(j)+" ");
System.out.println();
}
}구현 코드 - 2. 리스트 + 리스트
public static void main(String[] args) {
int[][] edges = new int[][] {
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
};
int n = 5;
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i = 0 ; i <= n ; i++) list.add(new ArrayList<>());
for(int[] edge : edges) {
list.get(edge[0]).add(edge[1]);
list.get(edge[1]).add(edge[0]);
}
//출력
for (int i = 1; i < list.size(); i++) {
for(int j = 0 ; j < list.get(i).size(); j++)
System.out.print(list.get(i).get(j)+" ");
System.out.println();
}
}출력 결과
2 3 4
1 3 5
1 2
1 5
2 4 🔎 그래프 순회
그래프 순회란 한 정점에서 출발하여 체계적으로 그래프의 모든 정점을 한번씩 방문하는 것이다. 대표적인 알고리즘으로 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)이 있다.
- 깊이 우선 탐색(DFS, Depth-First-Search)
- 정점 v 방문
- v의 인접 정점 중 아직 방문하지 않은 정점 w를 찾아 DFS를 재귀적으로 수행
- 너비 우선 탐색(BFS, Breadth-First-Search)
- 정점 v 방문 - 큐에 삽입
- v의 인접 정점 중 아직 방문하지 않은 정점을 차례대로 방문
- 2번 끝났다면 큐에 있는 정점 꺼내 2번 실행
BFS / DFS의 추가 설명은 아래 링크를 통해 볼 수 있다.
BFS / DFS 더 알아보기
🔎 최소 신장 트리
신장 트리란 그래프 G의 부분 그래프로서 G의 모든 정점을 포함하는 트리이다.
최소 신장 트리는 간선에 가중치가 주어졌을 때 G의 신장 트리 중 간선의 가중치 합이 최소가 되는 신장 트리이다.
최소 신장 트리 조건
1) 모든 정점으로 갈 수 있는 경로 있는 서브 그래프
2) 간선 가중치 합 최소
주어진 가중치 그래프에서 최소 신장 트리로 만드는 대표적인 알고리즘 2개가 있다.
1. 크루스칼(Kruskal) 알고리즘
2. 프림(Prim) 알고리즘
두 알고리즘 모두 탐욕법(Greedy)을 사용한다. 각 단계에서 최상의 선택을 하고, 한번 내린 결정을 번복하지 않는다.
//이후 추가 설명 링크 추가
🔎 최단 경로
최단 경로란 가중치 방향 그래프에서 출발지에서 도착지까지 경로의 간선 가중치 합이 최소인 경우다. 무방향 그래프인 경우 (v, w)와 (w, v) 다른간선으로 구분하여 구한다.
최단 경로 구하는 알고리즘
- 단일-소스 최단 경로: 한 정점에서 출발하는 최단 경로
1. 다익스트라(Dijkstra) 알고리즘
음수 가중치없다고 가정
시간복잡도:O(n^2)
2. 벨만-포드(Bellman-Ford) 알고리즘
음수 사이클없다고 가정
시간복잡도:O(nm)
- 모든-쌍 최단 경로: 모든 정점쌍에 대해 최단 경로
3. 플로이드-와샬 알고리즘
음수 사이클없다고 가정
시간복잡도:O(n^3)
인접 행렬 그래프 가정
가중치가 양수/음수 임의로 주어지면 NP-완전(NP-Complete)이다. 즉, 다항시간 알고리즘이 아니라 최단 시간을 구할 수 없으며 빨리 풀 수 없다.
좋은 글 잘 보았습니다!