-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
크루스칼 알고리즘 관련하여
21.07.23 22:11 작성 조회수 211
0
아래가 수업도중에 배운 알고리즘인데요!
------------------------------------------
int main(void)
{
int v, e, city_a, city_b, cost, i, res, cnt;
vector<Edge> Ed;
res = cnt = 0;
cin >> v >> e;
for (i = 1; i <= e; i++) {
unf[i] = i;
}
for (i = 0; i < e; i++)
{
cin >> city_a >> city_b >> cost;
Ed.push_back(Edge(city_a, city_b, cost));
}
sort(Ed.begin(), Ed.end());
for (i = 0; i < m; i++)
{
int fa = Find(Ed[i].v1);
int fb = Find(Ed[i].v2);
if (fa != fb) {
res += Ed[i].cost;
Union(Ed[i].v1, Ed[i].v2);
}
}
cout << res << endl;
return 0;
}
------------------------------------------
이 중에서 간선을 선택하는
for (i = 0; i < m; i++)
{
int fa = Find(Ed[i].v1);
int fb = Find(Ed[i].v2);
if (fa != fb) {
res += Ed[i].cost;
Union(Ed[i].v1, Ed[i].v2);
}
}
이 부분에 대해 궁금증이 있습니다!
크루스칼은 n개의 정점이 주어지면 n-1 개의 간선을 최소 가중치를 기준으로 선택하는 것으로 알고 있습니다.
그런데 문제에선 n-1개라는 기준을 사용하지 않았는데 그 이유가 있을까요? 선생님의 문제풀이에서 cnt 변수를 만드셨으나 사용하지 않으셨는데, 이를 체크하려다 체크하지 않으신 것 같습니다. 그 이유는 무엇인지 궁금합니다.
it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
78. 원더랜드 : Kruskal MST(최소스패닝트리) 알고리즘 : Union&Find 활용
강의실 바로가기
답변을 작성해보세요.
0
김태원
지식공유자2021.07.25
안녕하세요^^
N개의 정점으로 구성된 그래프에서 회로를 피하면서 N-1개의 간선을 선택하면 N개의 정점이 모두 연결된 트리가 됩니다. 즉 N개의 정점이 모두 한 집합이 되었다는 얘기입니다. 그러므로 N-1개의 간선이 선택된 이후부터는 for문이 계속 돌아도 if (fa != fb) 조건이 참이 되지 않아 더이상 간선이 선택되는 일은 없습니다.
답변 1