1. 최소 신장 트리(MST)에 대하여 설명해주세요.
- 최소신장트리는 모든 정점들이 사이클이 존재하지 않으면서 최소비용으로 연결되어 있는 트리입니다.
- 크루스칼 알고리즘과 프림 알고리즘이 대표적으로 있습니다.
- 크루스칼 알고리즘은 간선(Edge)들을 가중치(Weight)를 기준으로 정렬하여
가장 낮은 가중치를 가진 간선부터 선택하여 사이클이 없으면 트리에 추가하는 방식입니다.
- 프림 알고리즘은 임의의 정점(Node)을 트리에 추가하고
인접한 간선(Edge)들 중에 최소 가중치(Weight)인 경우에 트리에 추가하는 방식입니다.
2. 다익스트라 알고리즘에 대해서 설명해주세요.
- 최단 경로 알고리즘입니다. 네비 길찾기 등에서 사용됩니다.
- 출발지에서 각 정점까지의 거리를 기록해두고,
아직 방문하지 않은 정점 중 최소 비용 정점을 선택하면서
인접 정점의 거리를 갱신하는 과정을 반복하는 알고리즘입니다. - 우선순위 큐를 사용하면 효율적으로 구현할 수 있습니다.
- 만약, 음수 가중치가 있다면 사용할 수 없습니다.
그래프 이론 용어
- 그래프
정점과 간선의 집합 - 정점 (Node, Vertex)
스스로 존재할 수 있는 객체 - 간선 (Edge)
정점을 잇는 객체, 스스로 존재할 수 없는 객체 - 가중치 (Weight)
간선이 값을 가질 때, 간선을 사용하는 비용이라고도 함 - 방향 (Direction)
간선을 이용할 때, 제한이 있다는 의미라고도 함
최소 신장 트리 (Minimum Spanning Tree, MST)
모든 정점(Node)이 사이클 없이 최소 비용으로 연결되어있는 트리입니다.
신장트리
신장: 늘리다, 뻗어나가다 라는 뜻
모든 정점(Node)이 사이클 없이 연결된 트리를 뜻합니다.
실생활 예시
- 여러 기지국들이 있고, 최소 전선 비용으로 모든 기지국들을 연결할 때 활용할 수 있음
- 네트워크를 구축할 때, 데이터를 효율적으로 전송하기 위한 최소 비용의 네트워크 구조를 설계할 때 사용할 수 있음
최소 신장 트리 알고리즘
1. 크루스칼 알고리즘
간선(Edge)을 가중치(Weight) 기준으로 정렬한 뒤에
가장 낮은 가중치부터 트리에 추가하면서,
사이클을 만들지 않으면 트리에 추가하는 알고리즘입니다.
아이디어
- 그래프 간선들의 가중치를 기준으로 오름차순으로 정렬합니다.
- 가장 낮은 가중치(Weight)를 갖고 있는 간선(Edge)를 선택합니다.
- 해당 간선(Edge)이 사이클을 만들지 않는다면 트리에 추가합니다.
- 그래프 정점 개수(N)를 고려하여 간선이 N-1개가 될때까지,
혹은 모든 간선(Edge)에 대해서 2~3번을 반복합니다.
동작과정
- 위와 같은 신장 트리가 존재할 때,
간선(Edge)들 중에 가중치가 작은 1부터 트리에 추가하게 됩니다.
- 다음으로 가중치가 2, 3, 4인 간선(Edge)을 트리에 추가하고,
가중치 5인 간선(Edge)을 연결할 경우 사이클(3,4,5)이 생기므로
가중치 5를 가진 간선(Edge)은 트리에 추가하지 않습니다.
- 마찬가지로 가중치 6을 가진 간선(Edge)을 추가할 경우에도
사이클(2,3,4,6)이 생기므로 트리에 추가하지 않습니다.
- 이러한 과정들을 거쳐 위와 같은 최소 신장 트리(MST)가 구현됩니다.
수도코드
public Tree kruskal(List<Edge> graph){
Tree tree = new Tree();
graph = sortByWeightAsc(graph); // 간선(edge)의 가중치(weight)를 기준으로 오름차순 정렬
for (Edge edge: graph){
// MST의 Edge 개수 == (그래프의 Node 개수 - 1) 이면 반복문 종료
if(graph.getNodeSize() == (tree.getEdgeSize() - 1)){
break;
}
// 사이클이 생기면 다음 간선으로
if(tree.detectCycle(edge){
continue;
}
// 사이클이 아니면 간선(Edge) 추가
tree.add(edge);
}
return tree;
}2. 프림 알고리즘
시작할 정점을 정하고 인접한 간선들 중에 가중치가 적은 간선들을 트리에 추가하는 알고리즘입니다. 마찬가지로 사이클이 존재해선 안됩니다.
아이디어
- 시작하는 정점(Node)를 정하고 트리에 추가한다.
- 트리와 연결된 간선(Edge)들 중에
최소 가중치(Weight)인 간선을 트리에 추가한다. - 트리 집합이 정점개수(n)에 n-1개의 간선을 가지면 종료한다.
동작과정
- 시작하는 정점(Node)을 선택하고 트리에 추가합니다.
트리에 인접한 모든 간선(Edge)들 중에 최소 가중치(Weight)인 (1)을 선택합니다.
- 또 한번 트리에 인접한 모든 간선(Edge)들 중에 최소 가중치를 갖고 있는
(4)를 선택하여 트리에 추가합니다.
- 다음으로는 (3)을 선택하여 트리에 추가합니다.
- 다음으로 (2)를 선택하고, (10)을 선택하여 최소신장트리(MST)가 구현됩니다.
수도코드
public Tree prim(List<Edge> graph, Node startNode){
Tree tree = new Tree();
tree.setStart(startNode); // 시작하는 정점(Node) 설정
// 그래프의 Node 개수 == (트리의 Edge 개수 - 1)이면 반복문 종료
for(int i = 0; i < graph.getNodeSize() - 1; i++){
// 사이클이 생기면 다음 간선으로
if(tree.detectCycle(edge){
continue;
}
// 트리와 인접한 모든 간선(Edge) 중에 가중치(Weight)가 가장 낮은 간선 하나를 찾아 추가
Edge edge = findSmallestEdge(tree, graph);
tree.add(edge);
}
return tree;
}최단 경로 알고리즘
- 정점(Node) 간의 탐색 비용을 최소화하는 알고리즘입니다.
실생활에서 네비 길찾기 등으로 사용되는 알고리즘입니다. - 그래프에서 두 정점(Node) 사이를 연결하는 경로 중, 비용(Weight)의 합이 최소가 되는 경로를 찾는 알고리즘입니다.
다익스트라 알고리즘
- 시작 정점(Node)부터 모든 정점까지의 최단 경로를 구하는 알고리즘입니다.
- 출발지에서 각 정점들의 최소비용을 설정하고,
방문하지 않은 정점들 중에 최소 비용 정점을 선택해가며,
인접 정점들의 비용을 갱신하는 과정을 반복합니다. - 우선순위 큐를 사용하여 효율적으로 구현할 수 있습니다.
- 음수 가중치가 있는 경우 사용하기 어렵습니다.
아이디어
cost: 각 정점(Node)들의 최소 비용을 저장하고 있는 우선순위 큐
visit: 앞으로 방문해야 할 정점(Node)들을 저장하고 있는 객체
- 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.
- 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라,
우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
동작과정
- 출발 정점(Node)의 비용(cost)은 0, 나머지는 무한대/큰 값(∞)로 초기화합니다.
- 시작 정점을 방문하지 않은 곳(visit)에 저장합니다.
- visit에서 방문하지 않은 정점(Node)들 중 비용이 가장 적은 정점(SmallestNode)를
현재 정점(CurrentNode)로 설정합니다.
해당 정점은 visit에서 삭제합니다. (현재정점으로 방문했으니까) - 현재 정점(CurrentNode)와 인접한 정점(Node)들을 확인하며,
cost에 저장된 비용들과 비교하여 cost에 저장된 최소비용을 갱신합니다.
만약, 해당 인접한 정점(Node)을 방문하지 않았다면 visit도 갱신합니다. - 모든 정점(Node)을 방문할 때까지, 3~4 과정을 반복합니다.
- 시작 정점은 A로 설정하고, 해당 정점에서부터의 다른 정점들까지의 거리는 무한대로 설정한다.
- 시작 정점의 비용은 0으로 설정된다.
- 현재 정점(A)에서 방문할 수 있는 B, C의 비용을 최소비용으로 갱신한다.
- 현재 정점(A)에서 방문하지 않은 곳들(B, C) 중에서
가장 적은 비용을 갖고 있는 C(5)가 선택된다. - 현재 정점(C)에서 방문할 수 있는 B, D, E의 비용을 최소비용으로 갱신한다.
- 현재정점(C)에서 방문하지 않은 곳들(B, D, E) 중에서
가장 적은 비용을 갖고 있는 B(7), E(7) 중에서 임의로 선택한다. - 나는 B(7)을 선택했다.
- 현재정점(B)에서 방문할 수 있는 D의 비용을 최소비용으로 갱신한다.
- 아직 방문하지 않은 D, E 중에서 비용이 적은 D를 방문하고, 마지막으로 E를 방문한다.
- 위와같은 과정으로 각 정점까지의 최단 경로를 가진 트리가 완성이 되었다.
수도코드
public Map<Node, Long> djikstra(Graph graph, Node startNode){
final long INF = Long.MAX_VALUE / 4;
Map<Node,Long> cost = new HashMap<>();
// 1. 출발 정점(Node)의 비용(cost)은 0, 나머지는 무한대/큰 값(∞)로 초기화합니다.
for(Node node: graph.getNodes()){
cost.put(node, INF);
}
cost.put(startNode, 0);
// 2-1. 시작 정점(Node)을 방문하지 않은 곳(visit)에 저장합니다.
PriorityQueue<Node> visit = new PriorityQueue<>();
visit.add(startNode);
// 2-2. 이미 방문한 정점(Node)들을 저장하는 객체를 생성합니다.
List<Node> visited = new ArrayList<>();
while(!visit.isEmpty()){
// 3. 방문하지 않은 정점(Node)들 중, 비용이 가장 적은 정점(Node)을 현재정점(currentNode)으로 설정
Node currentNode = visit.poll();
visited.add(currentNode);
// 4-1. 현재정점(currentNode)과 인접한 정점(Node)들을 확인합니다.
for (Node neighborNode: currentNode.getNeighbors()){
// 4-2. 방문했던 정점(Node)이면, 스킵합니다.
if(visited.contains(neighborNode)) continue;
// 4-3. cost에 저장된 비용과 비교하여 최소비용을 갱신합니다.
Long tmpCost = currentNode.getCost() + currentNode.calCost(neighborNode);
if(cost.get(neighborNode) > tmpCost){
cost.put(neighborNode, tmpCost);
}
// 4-4. 방문하지 않았다면 방문해야 할 정점(visit)에 저장합니다.
visit.add(neighborNode);
}
}
return cost;
}출처
wannabe---ing