IM

작지만 단단하게

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.
https://github.com/ejImDev/data_structure_study.git

최소신장트리

  • 신장트리(Spanning Tree) : 주어진 그래프가 하나의 연결성분으로 구성되어 있을 때, 그래프의 모든 정점들을 싸이클 없이 연결하는 부분 그래프
  • 최소신장트리(Minimum Spanning Tree, MST) : 하나의 연결성분으로 이루어진 무방향 가중치 그래프에서 간선의 가중치의 합이 최소인 신장 트리
  • MST를 찾는 대표적인 알고리즘은 Kruskal, Prim, Sollin 알고리즘
    • 모두 그리디(Greedy) 알고리즘
  • 그리디 알고리즘 : 최적해(최솟값 또는 최댓값)를 찾는 문제를 해결하기 위한 알고리즘 방식들 중 하나로서, 알고리즘의 선택이 항상 ‘욕심내어’ 지역적인 최솟값(또는 최댓값)을 선택하며, 이러한 부분적인 선택을 축적하여 최적해를 찾음

Kruskal 알고리즘

  • 간선들을 가중치가 감소하지 않는 순서로 정렬한 후, 가장 가중치가 작은 간선을 트리에 추가하여 싸이클을 만들지 않으면 트리 간선으로 선택하고, 싸이클을 만들면 버리는 일을 반복하여 N-1개의 간선이 선택되었을 때 알고리즘을 종료
    • N은 그래프 정점의 수

  • Kruskal 알고리즘이 그리디 알고리즘인 이유 : 남아있는 (정렬된) 간선들 중에서 항상 ‘욕심 내어’ 가중치가 가장 작은 간선을 가져오기 때문

  • 순서
    1. 가중치가 감소하지 않는 순서로 간선 리스트 L을 만든다
    2. while(트리의 간선 수 < N-1)
    3. L에서 가장 작은 가중치를 가진 간선 e를 가져오고, e에서 L을 제거
    4. if(간선 e가 T에 추가하여 싸이클을 만들지 않으면)
    5. 간선 e를 T에 추가

Dijkstra 알고리즘

  • 최단경로 찾기는 주어진 가중치그래프에서 출발점으로부터 도착점까지의 최단경로를 찾는 문제

  • Dijkstra 알고리즘 : 출발점으로부터 각 정점까지의 최단거리 및 경로를 계산

  • 순서
    1. 배열 D를 ∞로 초기화시킨다. 단, D[s]=0이다.
    2. for(k=0; k<N; k++)
    3. 방문 안된 각 정점 i에 대해 D[i]가 최소인 정점 minVertex를 찾고, 방문한다
    4. for(minVertex에 인접한 각 정점 w에 대해서)
    5. if(w가 방문 안된 정점이면)
    6. if(D[minVertex] + 간선(minVertex, w)의 가중치 < D[w])
    7. D[w] = D[minVertex]+간선(minVertex, w)의 가중치 // 간선완화
    8. previous[w] = minVertex

### 수행시간

  • Dijkstra 알고리즘은 N번의 반복을 거쳐 minVertex를 찾고 minVertex에 인접하면서 방문되지 않은 정점들에 대한 간선완화를 시도
  • 이후 배열 D에서 minVertex를 탐색하는데 O(N) 시간이 소요되고, minVertex에 인접한 정점들을 검사하여 D의 원소들을 갱신하므로 추가로 O(N) 시간이 소요
  • 따라서 총 수행시간은 Nx(O(N)+O(N)) = O(N^2^)

Bellman-Foad 알고리즘

  • Dijkstra 알고리즘은 음수가중치를 가진 그래프에서 최단경로를 찾지 못함
  • Bellman-Foad 알고리즘은 음수가중치 그래프에서도 문제 없이 최단경로를 찾을 수 있음
  • 단, 입력그래프에 싸이클 상의 간선들의 가중치 합이 0보다 작은 음수싸이킬이 없어야 함
    • 만약 어떤 경로에 음수싸이클이 존재한다면, 음수싸이클을 반복할 수록 경로의 길이가 더 짧아지는 모순이 발생하기 때문

  • 핵심아이디어 : 입력그래프에 음수싸이클이 없으므로 출발점에서 각 정점까지 최단경로 상에 있는 간선의 수는 최대 N-1개이다. 따라서 각 정점에 대해 간선완화를 N-1번 수행하면 더 이상 간선완화로 인한 갱신이 있을 수 없다.

  • 순서
    1. 배열 D를 ∞로 초기화한다. 단, D[s] = 0, s는 출발점
    2. for(k=0; k<N-1; k++)
    3. 각 (i,j)에 대하여
    4. if(D[j] > (D[i]+(i,j)의 가중치))
    5. D[j] = D[i]+(i,j)의 가중치 // 간선완화
    6. previous[j] = i

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/yZD3up52MRE

Updated: