\ # 2020 겨울방학 합숙 훈련 \ # 최소 생 성 트 리 입문 (Minimum Spanning Tree) 코드 노트

지식 점 개술
정의.

사 이 드 밴드 권 의 무방 향 연결 도 G = (V, E), n = | V |, m = | E |

V 의 모든 정점 과 E 중 n - 1 개의 변 으로 구 성 된 무 방향 연결 서브 맵 은 G 의 생 성 트 리

라 고 불 린 다.

변 의 가중치 와 가장 작은 생 성 트 리 는 무방 향 그림 G 의 최소 생 성 트 리

로 불 린 다.

최소 생 성 트 리: 최소 스 패 닝 트 리, 즉 MS

나무

무 회로

n 개의 정점 은 반드시 n - 1 개의 변

이 있다.
생 성 트 리

모든 정점 포함

n - 1 개의 변 은 모두 그림 속 에 있다

변 권 과 최소

최소 생 성 트 리 의 n - 1 변, 변 권 을 합치 면 모든 생 성 트 리 중 가장 작은

크 루스 칼 (Kruskal) 알고리즘 (시간 복잡 도 O (mlogm))
알고리즘 사상 (욕심 - 욕심)
먼저 n 개의 정점 만 포함 하고 변 집 이 빈 자 도 를 만 들 고 자 도 에서 각 정점 을 각 나무의 뿌리 결점 으로 본 다음 에 그물 의 변 집 E 에서 가중치 가 가장 작은 변 을 선택한다. 만약 에 이 변 의 두 정점 이 서로 다른 나무 에 속 하면 자 도 를 넣 는 것 이다. 즉, 두 그루 의 나 무 를 한 그루 로 합성 하 는 것 이다. 반대로 이 변 의 두 정점 이 같은 나무 에 떨 어 졌 다 면.취 할 수 없 으 며, 다음 가중치 가 가장 작은 변 을 취하 여 다시 시도 해 야 한다.숲 속 에 나무 한 그루, 즉 서브 맵 에 n - 1 개의 변 이 들 어 있 을 때 까지 순서대로 유추 합 니 다.
실제 조작

집합 을 구축 하고 조사 하 며 각 점 마다 하나의 집합 을 구성한다 (집합 은 고리 가 되 는 지 아 닌 지 를 판단 하 는 데 사용)

모든 변 을 가중치 에 따라 작은 것 에서 큰 것 으로 정렬 하고 각 변 (x, y, z)

을 순서대로 스 캔 한다.

만약 에 x, y 가 같은 집합 (x, y 가 연결 되 었 음) 에 속 하면 이 변 을 무시 하고 다음 줄 을 계속 스 캔 합 니 다

그렇지 않 으 면 x, y 가 있 는 집합 을 합 쳐 z 를 답 에 추가 합 니 다

n - 1 개의 변 을 누적 할 때 까지 최소 생 성 나무 형성

#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e3+10;
int father[maxn];
int n,m,sum,cnt;
struct node
{
	int st;
	int ed;
	int w;
}edge[maxn];
bool cmp(node x,node y)
{
	return x.w<y.w;
}
void init()
{
	for(int i=1;i<=n;i++) father[i]=i;
	memset(edge,0,sizeof(edge));
}
int find(int x)
{
	return x==father[x]?x:father[x]=find(father[x]);
}
void kruskal()
{
	sum=0,cnt=0; 
	for(int i=1;i<=m;++i)
	{
		int fx=find(edge[i].st);
		int fy=find(edge[i].ed);
		if(fx==fy) continue;//             
		sum+=edge[i].w;
		father[fx]=fy;
		cnt++;//       ，           ，     n-1   
		if(cnt==n-1) return;
	}
}
int main()
{
	while(~scanf("%d %d",&m,&n)&&m)
	{
		init();
		for(int i=1;i<=m;i++) scanf("%d %d %d",&edge[i].st,&edge[i].ed,&edge[i].w);
		sort(edge+1,edge+m+1,cmp);//          
		kruskal();
		if(cnt==n-1) printf("%d
",sum);
		else printf("?
");
	}
}

프 림 (Prim) 알고리즘 (시간 복잡 도 O (n2))
알고리즘 사상 (탐욕 - 탐욕)
임의의 시간 에 최소 생 성 트 리 에 속 하 는 노드 집합 을 T 로 확정 하고 나머지 노드 집합 은 S 로 설정 합 니 다. 매번 에 가장 작은 한 변 (x, y, z) 을 찾 으 면 x * 8712 ° S, y * 8712 ° T 를 만족 시 킵 니 다.즉, 두 점 은 각각 S, T 의 가중치 가 가장 작은 변 에 속 한 다음 에 점 x 를 S 에서 삭제 하여 집합 T 에 넣 고 z 를 답안 에 누적 하 는 것 이다.
실제 조작

최소 생 성 트 리 집합 을 만 들 고 원점 부터 입 점 집합

최소 생 성 트 리 집합 을 찾 을 때마다 이 점 집합 에서 임의의 거리 가 가장 작은 점

을 찾 습 니 다.

찾 아 낸 점 을 최소 생 성 트 리 집합 에 넣는다

used 태그 그룹 수 를 통 해 과도 한 이전 여 부 를 표시 합 니 다

한 점 을 찾 을 때마다 ans 변 권 과 & mincost 배열 의 최소 거리

를 업데이트 합 니 다.

코드 줄 주석 참조

#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e3+10;
int cost[maxn][maxn];//    
int mincost [maxn];
//mincost[u]                u        
int T,n,m,x,y,ans;
bool used[maxn];//   i         
int prim()
{
	memset(mincost,inf,sizeof(mincost));//   ，      inf 
	memset(used,false,sizeof(used));//   ，                
	mincost[0]=0;//   0      
	ans=0;//                 
	while(1)
	{
		int v=-1;//           
		//                      
		for(int u=0;u<n;++u)
		{
			if(!used[u]&&(v==-1||mincost[u]<mincost[v])) v=u;
			/*
				  （        ） （              ）
				        ，    ，           inf
			*/
		}
		if(v==-1) break;//   ，                 
		used[v]=true;//                 
		ans+=mincost[v];
		for(int u=0;u<n;++u) mincost[u]=min(mincost[u],cost[v][u]);
		//       
		/*
			    ，         mincost inf   cost[0][u]
			cost[0][u] 0      （   ），u     
			
			             
			      ，                  
			      mincost，     inf
		*/
	}
	return ans;
}
int main()
{
	while(~scanf("%d %d",&n,&m)&&n+m);
	{
		for(int i=0;i<m;i++) scanf("%d %d %d",&x,&y,&cost[x][y]);
		printf("%d
",prim());
	}
	return 0;
}