목록최소 스패닝 트리 (1)

코딩성장스토리

최소 스패팅 트리 와 다익스트라 정리

오랜만에 문제를 풀다가 헷갈리는 부분들이 있어서 정리를 해본다.. 최소 스패팅 트리 모든 노드에서 가중치 합이 가장 작은 트리를 만드는 것 크루스칼 vs 프림 크루스칼 알고리즘 간선의 길이가 짧은 것 부터 시작해서 사이클이 생기지 않게 간선을 추가하는 방식 프림 알고리즘 한 시작 노드를 정한 후에 노드에 연결된 간선 중 최소 값을 선택하여 확장해나가는 방식 크루스칼 알고리즘 구현 // 유니온 파인트도 사이클 체크 int findparent(int x){ if(x==findparent(parent[x])){ return x; }else{ return parent[x]=findparent(parent[x]); } } void uni(int x,int y){ x=findparent(x); y=findparen..
백준 코딩 2023. 6. 29. 17:21
이전 Prev 1 Next 다음