[작은 33951 의 알고리즘 설명] 최소 생 성 트 리 알고리즘 - kruskal
8257 단어 알고리즘 설명최소 생 성 트 리알고리즘
최소 생 성 트 리 알고리즘 은 말 그대로 변 을 주 고 이 변 을 나무 로 연결 시 켜 이 나무의 변 권 과 최소 화 하 는 것 입 니 다.
그 러 고 보 니 이 알고리즘 은 사실 욕심 인 데 어떻게 욕심 을 내 겠 는가?다음은 우리 kruskal 알고리즘 을 소개 하 겠 습 니 다.물론 kruskal 을 제외 하고 Prim 도 최소 생 성 트 리 알고리즘 이지 만 개인 적 으로 kruskal 이 더 편리 하 다 고 생각 하기 때문에 저 는 kruskal 을 사용 하 는 경향 이 있 습 니 다.
Kruskal
이 알고리즘 은 매우 간결 하고 이해 하기 쉽다. 바로 한 무더기 의 가장자리 에서 그 중에서 가장 작고 고리 가 형성 되 지 않 은 n - 1 n - 1 - 1 개의 변 을 한 그루 의 나무 로 연결 하 는 것 이다. 이곳 의 n n n n 은 총 절 포인트 이다.
첫 번 째 단 계 는 모두 가 어떻게 하 는 지 알 고 있 을 것 이 라 고 믿 습 니 다. 바로 가중치 에 따라 작은 것 부터 큰 것 까지 정렬 하 는 것 입 니 다. 매번 순서대로 가장 자 리 를 선택 하 는 것 입 니 다. 하지만 절 차 를 밟 고 code 를 넣 습 니 다.
//L.E.M.T
int n,m;
scanf("%d%d",&n,&m);//n ,m 。
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].len);//x y ,len
}
sort(a+1,a+1+m,cmp);// :
자, 이것 이 간단 한 첫걸음 입 니 다.
다음은 이 알고리즘 의 관건 이다. 고리 가 되 는 지 아 닌 지 를 어떻게 판단 하 느 냐 하 는 것 이다.
우 리 는 이 문 제 를 수집 하여 해결 할 수 있다.
생각해 보 세 요. 만약 두 점 이 같은 집합 에 있다 면 두 점 이 같 을 수 있다 는 것 을 증명 할 수 있 습 니 다. 그러면 이 두 점 사 이 는 더 이상 연결 되 지 않 습 니 다. 그 렇 죠?그래서 우 리 는 집합 을 통 해 왼쪽 점 과 오른쪽 점 이 같은 집합 에 있 는 지 판단 하면 된다. 없 으 면 이 쪽 을 선택 할 수 있다.
코드 를 넣다
//L.E.M.T
int getfa(int x)// , ,
{
if (fa[x]==x)
{
return x;
}
fa[x]=getfa(fa[x]);// ,
return fa[x];
}
이상 은 병합 부분 입 니 다.
//L.E.M.T
for (int i=0;i<=n;i++)
{
fa[i]=i;// ,
}
int ans=0;
for (int i=1;i<=m;i++)
{
int xx=getfa(a[i].x);//
int yy=getfa(a[i].y);//
if (xx!=yy)// ,
{
fa[yy]=xx;
ans+=a[i].len;//
}
}
자, 이것 이 바로 이 간단 하고 알 기 쉬 운 알고리즘 입 니 다.
다음은 우리 가 시간의 복잡 도 를 분석 해 볼 수 있다.
시간 복잡 도
앞의 정렬 은 O (m O (m l o g log m) m 이 고, 뒤의 정렬 은 O (m O (m l o g log n) n) 이다.
그러면 합치 면 O (m O (m l o g log m + m m + m m + m l o g log n) n) 이다.
1005 10 ^ 5 105 레벨 의 데 이 터 를 달 리 는 것 은 여전히 가 볍 고 느슨 하 다. 1006 10 ^ 6 106 레벨 의 데이터 카드 를 달 리 는 것 도 자주 지나 갈 수 있 을 것 이다.
자, 이제 이 간단 한 알고리즘 을 다 말 했 습 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
7 - 10 도로 촌 촌 통 (30 분) 자바 버 전이것 이 바로 가장 짧 은 길 입 니 다. 순 서 를 정 하고 start 와 end 를 찾 으 면 됩 니 다. c++ 로 하면 10 분 이면 끝 낼 수 있 을 것 같 습 니 다. 하지만 이번 학기 에 자바 를 배 우...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.