data structures - 프림 알고리즘 ( Prim's algorithm )

프림알고리즘이란 무엇인가?

크루스칼 알고리즘과 같이 minimum spanning tree 를 찾는 알고리즘이다
보통 우선순위 큐를 사용한다. 크루스칼 알고리즘과 같은 용도이지만, 응용 상황에서 두 알고리즘의 효율성이 달라질 수 있기 때문에 둘 모두 알아두는 것이 좋다.

단계별로 표현하자면

1. 그래프를 연결되어있는 node와 cost(가중치)순으로 만들어준다 그리고 가중치 기준으로 정렬해준다.
2. 우선순위큐를 만들어주고 시작노드를 넣어준다(순서상관이 없다 아무거나 넣어주면 된다)
3. 방문한 노드를 체크해줄수있게 visitTable을 만들어준다.
4. 우선순위큐가 빌때까지 순회하면서 방문하지 않은곳을 방문체크를 해준다. (cost값은 기호에 맞게 사용한다 문제 상황이 다르기때문에..)