그래프
정점들의 집합 v와 간선들의 집합 e로 구성된 자료구조
정점의 위치정보나 간선의 순서등은 그래프의 정의에 포함되지 않음
🥑 그래프의 종류
방향그래프 간선이 ‘방향’이라는 새로운 속성을 가짐
| 무향그래프 | 간선에 방향이 없는 그래프 |
| 가중치 그래프 | 간선에 ‘가중치’라는 실수 속성을 부여 |
| 다중 그래프 | 두 정점 사이에 두개 이상의 간선이 있을 수 있는 그래프 |
| 단순 그래프 | 두 정점 사이에 최대 한개의 간선만 있는 그래프 |
| 트리 혹은 루트없는 트리 | 부모 자식 관계가 없을 뿐 간선들의 연결 관계는 무향 그래프 |
| 이분 그래프 | 그래프의 정점들을 겹치지 않는 두개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점 간에만 간선이 존재하도록 만들 수 있는 그래프 |
🥑 그래프의 경로
단순경로 : 경로 중 한 정점을 최대 한 번만 지나는 경로
사이클/회로 : 시작한 점에서 끝나는 경로
🥑 그래프 사용 예
철도망의 안정성 분석 절단점 찾기 알고리즘
| 소셜 네트워크 분석 | BFS |
| 인터넷 전송속도 계산 | 최소 스패닝 트리 |
| 한붓 그리기 | 오일러 경로 → DFS |
| 외환 거래 | 최단거리(가중치) |
🥑 인접 행렬과 인접 리스트
인접 행렬 2차원 배열을 활용해 그래프이 간선 정보 저장. adjacent[i,j]는 정점 i에서 정점 j로 가는 간선이 있는지 나타냄. 가중치가 있다면 간선의 정보에 정수나 실수 변수를 두면 됨.
| 인접 리스트 | 각 정점 마다 해당 정점에서 나가는 간선의 목록을 저장해서 그래프 표현 |
인접행렬의 시간복잡도는 V*V 배열을 사용하기에 O(V^2)
인접리스트의 시간복잡도는 V개의 연결리스트에 실제 간선 수만큼 원소가 들어있기에 O(V+E) 공간만큼 사용
📌 그럼 언제 인접 행렬을 쓰고 언제 인접 리스트를 쓸까요?
간선의 수가 V^2에 비해 훨씬 적은 그래프를 희소 그래프, 간선의 수가 V^2에 비례하는 그래프를 밀집 그래프라고 함.
희소 그래프 → 인접리스트 , 밀집 그래프 → 인접행렬
🥑 오일러 서킷
- 그래프의 모든 간선을 정확히 한번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제
- 한붓그리기
- 무향그래프, 방향그래프에서 모두 해결 가능.
- 중복정점 허용 (모든 정점의 차수는 짝수)
- 어떤 그래프 G가 오일러 순회를 가지기 위한 필요충분조건은 G가 연결 그래프이고, 모든 정점들이 짝수 개의 차수를 가져야 한다.
무향 그래프 방향 그래프
| • 모든 정점이 짝수개여야 함. (들어가는 횟수와 나가는 횟수가 같아야 하기 때문) | |
| • 모든 간선이 하나의 컴포넌트여야 함. | |
| • 각 정점에 인접한 간선이 짝수개여야 함. (짝수점) | • 각 간선은 둘 중 한 방향만 쓸 수 있기 때문에 각 정점에 들어오는 간선의 수와 나가는 간선의 수가 같아야만 한다. |
| • 모든 정점이 짝수개여야 함. (들어가는 횟수와 나가는 횟수가 같아야 하기 때문) | |
| • 모든 간선이 하나의 컴포넌트여야 함. |
+) 한 정점에 인접한 간선의 수를 해당 정점의 “차수”라고 함. 차수가 짝수인 정점을 “짝수점”, 차수가 홀수인 정점을 “홀수점”이라고 함.
🥑 오일러 트레일 (오일러 경로)
- 모든 간선을 정확히 한번씩 지나지만 시작점과 끝점이 다른 경로
- 시작점과 끝점을 제외한 모든 점이 짝수점이고, 시작점과 끝점은 홀수점이여야 한다.
- 어떤 그래프 G가 오일러 경로(트레일)를 가지기 위한 필요충분조건은 G가 연결 그래프이고, 홀수 차수의 개수가 0 또는 2여야 함.
관련문제를 풀어보자!
백준 1199
https://www.acmicpc.net/problem/1199
백준 16168
백준 1178
백준 17414
REF
https://hy38.github.io/posts/euilerian-circuit-and-trail/
https://aren227.me/eulerian-circuit-and-trail/
🥑 해밀토니안 순회
- 모든 정점을 정확히 한번씩 지나가서 시작점으로 돌아옴(모든 간선을 통과하지 않아도 됨)
🥑 해밀턴 패스 (해밀턴 경로)
- 시작점과 끝점이 다르지만 모든 정점을 한번씩 방문한다.
REF
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=qbxlvnf11&logNo=221361498110
https://algorfati.tistory.com/140
📌 DFS
시간복잡도 : O(n)
재귀적 특징, 백트래킹, 완전탐색(조합,순열) → 하나하나 다 탐색하는 경우
📌 BFS
깊이의 특징을 이용한 문제 (최단경로→ 가중치가 같은 그래프에서 ) , 영역끼리 묶는 경우
시간복잡도 : O(n)
움직여야 하는 최소칸의 개수
움직이는 횟수 배열을 만들어서 누적합으로 구현
cnt배열을 만들어서 cnt[nX+dirX[s]][cntnY+dirY[s]]=cnt[nX][nY]+1;
🐳최소 스패닝 트리
📌 스패닝 트리란 무엇일까?
- 그래프의 최소 연결부분 그래프이다. (최소연결부분== 간선의 수가 가장 적다)
- n개의 정점을 가지고 있는 그래프의 최소 간선의 수는 n-1개이고, n-1개의 간선으로 연결되어있으면 필연적으로 트리형태가 되는데, 이것이 스패닝 트리가 된다.
- 그래프의 일부 간선을 선택해서 만든 트리
- 하나의 그래프에는 많은 신장트리가 존재할 수 있다.
- 모든 정점이 연결되어있으며, 사이클을 포함해서는 안된다.
📌 최소 스패닝 트리란?
- 간선의 가중치의 합이 최소여야 한다.
- 단순히 적은 간선을 사용한다고 해서 최소비용이 아니다.
- 간선이 적으면 크루스칼, 간선이 많으면 프림 알고리즘을 사용한다.
🐋크루스칼 알고리즘
유니온파인드의 좋은 사용예이다.
- 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
- 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다
- 모든 간선에 대하여 2번의 과정을 반복한다.
class Node implements Comparable<Node>{
int to;
int from;
int value;
public Node(int to, int from, int value) {
this.to = to;
this.from = from;
this.value = value;
}
@Override
public int compareTo(Node o) {
return this.value - o.value;
}
}
public class Main {
private static int n;
private static int[] parents;
public static void main(String[] args) {
n = 7;
int[][] graph = {{1,2,29}, {1,5,75},{2,3,35},{2,6,34}, {3,4,7},{4,6,23},
{4,7,13}, {5,6,53}, {6,7,25}};
parents = new int[n + 1];
for (int i=1; i<n+1; i++) {
parents[i] = i;
}
Queue<Node> pq = new PriorityQueue<>();
for(int i=0; i<graph.length; i++) {
int to = graph[i][0];
int from = graph[i][1];
int value = graph[i][2];
// 우선순위 큐는 자동으로 간선 비용순(오름차순)으로 정렬된다.
pq.add(new Node(to, from, value));
}
int size = pq.size();
int total =0;
// 간선 하나씩 조회 (비용이 작은 간선부터)
for(int i=0; i< size; i++) {
Node node = pq.poll();
int rx = find(node.to);
int ry = find(node.from);
// 사이클이 발생하지 않는 경우에만 집합에 포함
if(!isSameParent(rx, ry)) {
total += node.value;
union(node.to,node.from);
}
}
System.out.println(total);
}
static int find(int x) {
if (parents[x] == x) {
return x;
}
return parents[x] = find(parents[x]);
}
static void union(int x, int y) {
x = find(x);
y = find(y);
// 더 find 값으로 부모 노드 설정
if (x < y) {
parents[y] = x;
}
else {
parents[x] = y;
}
}
static boolean isSameParent(int x, int y) {
if(x == y) return true;
return false;
}
}
🐋 프림 알고리즘
다익스트라 알고리즘과 비슷한 형태를 띄고 있다.
- 임의의 간선을 선택한다.
- 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택한다.
- 모든 정점에 대하여 2번의 과정을 반복한다.
++) 양방향 간선을 쓴다.
class Node implements Comparable<Node>{
int to;
int value;
public Node(int to, int value) {
this.to = to;
this.value = value;
}
@Override
public int compareTo(Node o) {
return this.value - o.value;
}
}
public class Main {
static int total;
static List<Node>[] list;
static boolean[] visited;
public static void main(String[] args){
int v = 7;
int[][] graph = {{1,2,29}, {1,5,75},{2,3,35},{2,6,34}, {3,4,7},{4,6,23},
{4,7,13}, {5,6,53}, {6,7,25}};
list = new ArrayList[v+1];
visited = new boolean[v+1];
for(int i=1; i<v+1; i++) {
list[i] = new ArrayList<>();
}
for(int i=0; i<graph.length; i++) {
int a = graph[i][0];
int b = graph[i][1];
int w = graph[i][2];
list[a].add(new Node(b,w));
list[b].add(new Node(a,w));
}
prim(1);
System.out.println(total);
}
static void prim(int start) {
Queue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start,0));
while(!pq.isEmpty()) {
Node p = pq.poll();
int node = p.to;
int weight = p.value;
if(visited[node]) continue;
// 선택한 간선의 정점으로부터 가장 낮은 가중치 갖는 정점 선택
visited[node]= true;
total += weight;
for(Node next : list[node]) {
if(!visited[next.to]) {
pq.add(next);
}
}
}
}
}
REF
https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html
https://loosie.tistory.com/159
- 0-1 BFS 알고리즘
🐋다익스트라 (그리디)
특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘.
→ 우선순위 큐 방법
🐋플로이드 알고리즘 (DP)
모든지점에서 다른 모든 지점까지의 최단경로를 모두 구한다. 모든 노드에 대하여 최단거리를 담아야 하므로 2차원 배열이 필요하고,3중 for문을 쓴다는 특이점을 가진다.
arr[a][b]=Math.min(arr[a][b],arr[a][k]+arr[k][b]);
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Main{
public static int n;
public static int m;
public static int arr[][];
public static int INF=1000000000;
public static void main(String[]args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n=Integer.parseInt(br.readLine());
m=Integer.parseInt(br.readLine());
arr=new int[n+1][n+1];
//무한으로 초기화
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
arr[i][j]=INF;
}
}
//자기자신으로 가면 0
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j){
arr[i][j]=0;
}
}
}
//입력받기
for(int i=0;i<m;i++){
st=new StringTokenizer(br.readLine());
int a= Integer.parseInt(st.nextToken());
int b=Integer.parseInt(st.nextToken());
int c=Integer.parseInt(st.nextToken());
arr[a][b]=Math.min(arr[a][b],c);//노선이 여러개일 경우 원래있던값이랑 새로운값 중 비교
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
arr[j][k]=Math.min(arr[j][k],arr[j][i]+arr[i][k]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(arr[i][j]==INF){
System.out.print("0"+" ");
}
else{
System.out.print(arr[i][j]+" ");
}
}
System.out.println();
}
}
}
'자료구조,알고리즘 개념정리' 카테고리의 다른 글
| [재귀] 하노이탑 이동순서 이해하기 (0) | 2022.07.01 |
|---|
댓글