生成樹算法

生成樹

• 最小生成樹
• • 一、prim算法
  • 二、Kruskal 算法
• 最大生成樹
• 次小生成樹

約定：下文的代碼中，m為邊的個數，n為點的個數

最小生成樹

我們定義無向連通圖的 最小生成樹（Minimum Spanning Tree，MST）為邊權和最小的生成樹。

注意：隻有連通圖才有生成樹，而對于非連通圖，隻存在生成森林（好多生成樹！）。

圖的形式不唯一，但是保證邊權和最小！！

一、prim算法

基于鄰接矩陣的算法，對于密集圖更為友善，且複雜度達到O(N*N),且受到鄰接矩陣特性的時間空間限制

記錄目前在樹上的所有點，并維護該樹（聯通塊）對外界的所有邊的權值

dist [ x ]

增邊：每次選取最小的

dist

加入該聯通塊

維護的過程是：每加入一個點，周遊它的所有（目前聯通塊外）出邊，取這條出邊的邊權和

dist

的最小值更新

dist

數組

int prim(){
	
	memset(dist, 0X3f , sizeof dist);     初始化距離均為最大值
	int ans=0; 
	dist[1]=0;                             首點到自己距離為0 
	for(int i=1;i<=n;i++)
	{
		int tt=-1;                         初始化沒有選中的點
		
		for(int j=1;j<=n;j++)              枚舉所有的單點
		{
			if(!vis[j]&&(tt==-1||dist[tt]>dist[j]))tt=j;    取距離最小的單點（可以用優堆優化了！）
		}	
		
		vis[tt]=true;
		ans+=dist[tt];
		
		for(int i=1;i<=n;i++)dist[i]=min(dist[i],g[tt][i]);
	}
	return ans;
} 

           

注意事項：

• 最大值不能初始化過大：如果是int類型:

  0X7f

  到

  0X3f

  即可，過大可能會溢出
• 最後的修改時可以隻修改沒有通路過的節點的加一句判斷

  if(!vis[i] )

• 典例：AcWing 1140. 最短網絡

二、Kruskal 算法

以三元組（出邊，入邊，邊權）的形式存邊，便于後期對邊進行排序

排序後，從小到大枚舉每一條邊，判斷他的兩條邊是不是統一集合（同一聯通塊）

判斷集合相同性的代碼基于并查集！

分情況：

1，如果是，跳過

2，不是，集合合并，把邊加進來

int kruskal()
{
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		int f=a[i].f;
		int w=a[i].w;
		int t=a[i].t;
		
		int a=getfa(f);
		int b=getfa(t);
		if(a!=b)fa[a]=b,ans+=w;
	}
	return ans;
}
           

幾點注意：

1，變量的命名一定要注意避免重名

2，并查集集合合并的操作合并的是根節點，修改的對象也是根節點的父親

• 典例：AcWing 1141. 區域網路

最大生成樹

最大生成樹算法和最小并無差別，隻需把cmp函數的

<

改成

>

即可

特性：加入的邊數限制

k

，在kruskal算法中加入邊數的計數器

op

若是等于

k

即刻跳出并輸出答案

注意：最大spanning tree不一定聯通所有點

• 典例：洛谷 P2121 拆地毯
• 典例解答： AC代碼

次小生成樹