[작은 33951 의 알고리즘 설명] 최소 생 성 트 리 알고리즘 - kruskal

알고리즘 설명
최소 생 성 트 리 알고리즘 은 말 그대로 변 을 주 고 이 변 을 나무 로 연결 시 켜 이 나무의 변 권 과 최소 화 하 는 것 입 니 다.
그 러 고 보 니 이 알고리즘 은 사실 욕심 인 데 어떻게 욕심 을 내 겠 는가?다음은 우리 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 레벨 의 데이터 카드 를 달 리 는 것 도 자주 지나 갈 수 있 을 것 이다.
자, 이제 이 간단 한 알고리즘 을 다 말 했 습 니 다!