최소신장트리를 찾는 알고리즘인데, 이거 기억이 안나는데

prim algorithm은 임의의 node 하나에서 시작해서 연결되는 node들을 하나씩 추가해나가는데,

node를 추가하는 건 가능한(= 이미 선택된 node와 이웃한 노드) edge중에서 weight가 가장 작은 것을 추가하는 거라던데,


구글 보면서 내가 이해한대로는,


임의의 Node P를 시작점으로 받고 최소경로는 일단 아무 경로도 없으니 0으로 세팅한다.

그다음 선택된 정점의 정보를 담은 배열인 S에 시작점인 P를 넣는다.

그리고 이미 P는 선택되었으니 node추가는 n-1번하는데,

반복문을 돌때마다 e (= edge)는 (u,v) (= 이미 선택된 node인 u와 선택되지 않은 노드 v, 즉 이미 선택된 node와 이웃한 node랑 연결한 경로) 중 가장 가중치가 작은 경로를 선택하고,

그다음 MST인 T에 경로를 추가하고 (ex_ {(a,b), (a,c) ..) 이번에 선택된 노드인 v를 T에 넣고..

그걸 모든 노드가 선택될때까지 반복하는거구........ 우우........


암튼 첨에 글쓸때는 긴가민가했는데 막상 글쓰니까 제대로 이해한거같기도? 암튼 아님말고?

우우우 구글에서 나오는 의사코드보다 훨씬 간결하게 설명해주셔서(1학년 수업임 ㅇㅇ) 몬가 코드로 구현해보고싶긴한데 빡셀거같기도 아님말고?