다익스트라 알고리즘은 도로 네트워크 등을 나타낼 수 있는 그래프에서 노드 간의 최단 경로를 찾는 알고리즘입니다.

이 알고리즘은 다양한 형태로 존재합니다. 다익스트라의 원래 형태는 두 노드 간의 최단 경로를 찾았지만, 더 일반적인 형태는 단일 노드를 "소스"노드로 수정하고 그래프의 소스에서 다른 모든 노드까지의 최단 경로를 찾아 최단 경로 트리(shortest-path tree)를 생성합니다.


`a`와`b` 사이의 최단 경로를 찾는 다익스트라 알고리즘입니다.

가장 낮은 거리를 가지며 방문하지 않은 정점(vertex)를 선택하고, 이를 통해 방문하지 않은 각 이웃까지의 거리를 계산하며, 더 작은 경우 이웃의 거리를 업데이트합니다. 이웃에 대한 작업을 마치면 방문한 것으로 표시(빨간색으로 변경)합니다.

-[Wikipedia](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)

-[On YouTube by Nathaniel Fan](https://www.youtube.com/watch?v=gdmfOwyQlcI&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

-[On YouTube by Tushar Roy](https://www.youtube.com/watch?v=lAXZGERcDf4&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

_Read this in other languages:_

[_한국어_](README.ko-KR.md)

Dijkstra's algorithm is an algorithm for finding the shortest

paths between nodes in a graph, which may represent, for example,

road networks.

크루스칼 알고리즘은 두 트리를 연결하는 최소 간선 가중치를 찾는 최소 신장 트리 알고리즘입니다.

각 단계에서 비용을 더하는 연결된 가중 그래프에 대한 최소 신장 트리를 찾기 때문에 그래프 이론에서의 그리디 알고리즘입니다. 즉, 트리의 모든 간선의 총 가중치가 최소화되는 모든 정점을 포함하는 트리를 형성하는 간선의 하위 집합을 찾습니다. 그래프가 연결되어 있지 않으면 최소 신장 포레스트(연결된 각 구성 요소의 최소 신장 트리)를 찾습니다.



유클리드 거리를 기반으로 한 크루스칼 알고리즘의 데모입니다.

**최소 신장 트리(MST)** 또는 최소 가중치 신장 트리는 연결된 간선 가중치 무 방향 그래프의 간선의 하위 집합으로, 사이클 없이 가능한 최소 총 간선 가중치로 모든 정점을 연결합니다. 즉, 간선 가중치의 합이 가능한 작은 신장 트리입니다. 보다 일반적으로, 간선-가중치 비방향 그래프(꼭 연결되지는 않음)에는 연결된 구성 요소에 대한 최소 신장 트리의 결합인 최소 신장 포레스트(minimum spanning forest)가 있습니다.


평면 그래프와 해당 최소 신장 트리입니다. 각 간선은 가중치로 레이블이 지정되며, 이 값은 길이에 거의 비례합니다.


이 그림은 그래프에 최소 신장 트리가 두 개 이상 있을 수 있음을 보여 줍니다. 그림에서 그래프 아래의 두 트리는 주어진 그래프에서 최소 신장 트리가 될 수 있는 두 가지 경우입니다.

-[Minimum Spanning Tree on Wikipedia](https://en.wikipedia.org/wiki/Minimum_spanning_tree)

-[Kruskal's Algorithm on Wikipedia](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm)

-[Kruskal's Algorithm on YouTube by Tushar Roy](https://www.youtube.com/watch?v=fAuF0EuZVCk&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

-[Kruskal's Algorithm on YouTube by Michael Sambol](https://www.youtube.com/watch?v=71UQH7Pr9kU&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

_Read this in other languages:_

[_한국어_](README.ko-KR.md)

Kruskal's algorithm is a minimum-spanning-tree algorithm which

finds an edge of the least possible weight that connects any two

trees in the forest. It is a greedy algorithm in graph theory

컴퓨터사이언스에서 힙은 특수한 트리구조의 데이터 구조로 다음과 같은 특성을 갖고 있습니다.

컴퓨터과학에서의**힙**은 아래에 설명된 힙 속성을 만족하는 전문화된 트리 기반 데이터구조입니다.

*최소 힙* 에서는 만약`P`가`C`의부모노드일 경우,`P` 키(값)는`C` 키보다 작거나동일합니다.

*최소 힙*에서`P`가`C`의상위 노드라면`P`의 키(값)는`C`의 키보다 작거나같습니다.


-*최대 힙*에서`P` 키는`C` 키보다 크거나동일합니다.

*최대 힙*에서`P`의 키는`C`의 키보다 크거나같습니다.


- 힙의 "최상단" 노드에는 부모노드가 존재하지 않으며, 루트노드라고 부릅니다.

상위 노드가 없는 힙의 "상단"에 있는 노드를 루트 노드라고 합니다.

-[Wikipedia](<https://en.wikipedia.org/wiki/Heap_(data_structure)>)

-[YouTube](https://www.youtube.com/watch?v=t0Cq6tVNRBA&index=5&t=0s&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

컴퓨터 과학에서**우선 순위 큐**는 일반 큐 또는 스택 데이터 구조와 같은 추상 데이터 유형이지만, 여기서 각 요소에는 "우선 순위"가 연결됩니다.

우선 순위 큐에서는 우선 순위가 높은 요소가 낮은 요소 앞에 제공됩니다. 두 요소가 동일한 우선 순위를 가질 경우 큐의 순서에 따라 제공됩니다.

우선 순위 큐는 종종 힙을 사용하여 구현되지만 개념적으로는 힙과 구별됩니다. 우선 순위 대기열은 "리스트(list)" 또는 "맵(map)"과 같은 추상적인 개념입니다;

리스트가 링크드 리스트나 배열로 구현될 수 있는 것처럼 우선 순위 큐는 힙이나 정렬되지 않은 배열과 같은 다양한 다른 방법으로 구현될 수 있습니다.

-[Wikipedia](https://en.wikipedia.org/wiki/Priority_queue)

-[YouTube](https://www.youtube.com/watch?v=wptevk0bshY&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&index=6)

[_Русский_](README.ru-RU.md),

[_日本語_](README.ja-JP.md),

[_Français_](README.fr-FR.md),

[_Português_](README.pt-BR.md)

[_Português_](README.pt-BR.md),

[_한국어_](README.ko-KR.md)

In computer science, a**priority queue** is an abstract data type

which is like a regular queue or stack data structure, but where