어제는 최소 신장 트리를 구현하는 방법 중 하나인 크루스칼 알고리즘을 봤는데
오늘도 마찬가지로 최소 신장 트리를 구현하는 방법인 프림 알고리즘에 대해서 적어보려고 한다.
프림 알고리즘은 시작 노드를 기준으로 가장 낮은 가중치에 해당하는 노드로 진행하며 각각의 노드들과 연결된 가중치 중 작은 값을 선택하면서 진행하는 방식으로 이루어진다.
아래는 인접 행렬 형식의 그래프에서 프림 알고리즘을 작성한 코드이다.
function primMST(graph) {
const mst = new Array(graph.length).fill(null);
const key = new Array(graph.length).fill(Infinity);
const mstSet = new Array(graph.length).fill(false);
key[0] = 0;
mst[0] = -1;
for (let count = 0; count < graph.length - 1; count++) {
const u = minKey(key, mstSet);
mstSet[u] = true;
for (let v = 0; v < graph.length; v++) {
if (graph[u][v] !== 0 && mstSet[v] === false && graph[u][v] < key[v]) {
mst[v] = u;
key[v] = graph[u][v];
}
}
}
for (let i = 1; i < graph.length; i++) {
console.log(`${mst[i]} - ${i}\t${graph[i][mst[i]]}`);
}
}
function minKey(key, mstSet) {
// console.log('key', key);
// console.log('mstSet', mstSet);
let min = Infinity;
let minIndex = -1;
for (let v = 0; v < key.length; v++) {
if (mstSet[v] === false && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}순서대로 뜯어보면
mst는 해당 인덱스 번호의 값의 노드가 어디와 연결이 됐는지 표시해줄 배열이다.
key값은 가중치가 들어갈 예정이며
mstSet은 노드의 방문 여부를 기록한다.
key[0] = 0; / mst[0] = -1 부분은 시작지점을 잡아주는 과정이다.
for문으로 들어가게되면 u에 minkey함수의 반환값을 담아준다.
minkey 함수를 보면
최초에 min을 Infinity로 할당해주는 과정이 존재하는데, 이는 최소값을 선별하기 위함이다.
minKey 내부의 for문을 돌면서 key[v]값이 min보다 작을 경우 min값을 key[v]로 초기화 해주면서 최종적으로 minIndex안에 해당되는 v값을 반환해주고 이는 u에 할당된다.
u가 minKey함수를 통해 결정되면
mstSet[u]의 값을 true로 할당해주어 방문했음을 표시한다.
graph[u][v]가 0이 아닌지(자기자신) / mstSet[v]가 false가 맞는지(방문여부) / graph[u][v]가 key[v]보다 작은지(최소값)을 판별하여 조건을 충족할 경우
mst[v]값에 u를 기록하고(mst[v]위치의 노드가 u와 연결됐음을 의미)
key[v] 안에 graph[u][v]값을 기록한다.(연결 됐을 때의 가중치 값을 기록)
위와 같은 로직을 반복하여 최종적으로
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5
을 반환하게 된다.
(0노드와 1노드가 2의 가중치로 연결, 1노드와 2노드가 3의 가중치로 연결, 0노드와 3노드가 6의 가중치로 연결, 1노드와 4노드가 5의 가중치로 연결)
이렇게 0번 노드에서 출발 했을 때 특정 노드까지 갈 수 있는 최단 거리를 구할 수 있게 된다.
빨간색 굵은 선으로 작성된 부분이 선택된 간선이다.
싸이클이 형성되지 않았으며 0번 노드 기준으로 가장 적은 가중치로 연결되어있다.
(무방향 그래프이기 때문에 최단거리임은 서로 성립한다.)
스터디 원이 가져온 코드라서 직접 작성한건지 다른 블로그에서 가져온 것인지 출처를 알 수 없습니다... 만약 다른 분 코드였다면 덕분에 많이 배웠습니다. 감사해요
