差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:namespace:最小生成树 [2020/07/10 16:59]
great_designer 创建
+++ 2020-2021:teams:namespace:最小生成树 [2020/07/10 17:37] (当前版本)
great_designer [Prim算法（反圈法）]
@@ 行 1: / 行 1: @@
 ======最小生成树======
+=====引言=====
 图论的基础内容，例如稀疏图用邻接链表，稠密图用邻接矩阵，DFS、BFS和Dijkstra都已经写过了，一个重要工具并查集也写过了。那么接下来，本文是图论的核心内容：最小生成树。
@@ 行 7: / 行 9: @@
 接下来会简要阐述算法部分：Prim算法（又称反圈法或割集法），可以使用优先队列优化，适用于稠密图，因此常与邻接矩阵搭配；Kruskal算法（避圈法），必须采用并查集优化，适用于稀疏图，因此常与邻接链表搭配。
-其他不常见的算法例如Rosenstiehl算法（破圈法），因为难以优化，不如上两种算法好，已经被弃用了。
+其他不常见的算法例如Rosenstiehl算法（破圈法），因为难以优化，不如上两种算法好，已经被弃用了，因此不讲。
+=====割集（反圈）=====
+割集（反圈）：将图的顶点集划分为两部分，连接两部分的全体边构成割集。将图G的顶点集合V分成非空两部分，S和V-S。图G中连接S和V-S两部分的边的全体，称为G的一个反圈。
+简单地来讲，反圈刻画了图G两部分顶点间的连通性。如果这两部分顶点之间连通性强，那么对应的反圈的边数多。同样地，如果这两部分顶点之间连通性弱，那么对应的反圈的边数少。
+因此有一个简单结论：
+对于图G的支撑子图H，如果H连通，那么H与G的任意一个反圈有公共边。如果H不连通，那么存在G的反圈与H无公共边。
+这个模型称为“反圈”的原因，与下面的结论有关。
+设T是图G=(V,E)的一个支撑树，则T满足以下特征：
+T中没有圈，G-E(T)中没有G的反圈。
+**T添加任何一条边后，图中的边包含且仅包含一个圈，称为G关于T的一个基本圈。**
+**对于T中任意一条边e，G-E(T)-e中包含且仅包含G的一个反圈，称为G关于T的一个基本反圈。**
+只需要解释基本反圈的唯一性。事实上这个命题等价于：
+从树中任意去掉一条边，恰好包含两个分支。
+因此仅当反圈选择的两部分顶点恰好为这两个分支的时候，才能与去掉一条边的树恰好没有公共边。
+基本割集（反圈）：生成树的每条树枝对应一个基本割集。
+割集与生成树至少有一条公共边。
+圈与割集有偶数条公共边。
+圈在生成树外至少有一条边。
+基本圈中的弦，位于圈中树枝的每一个基本割集，不在其他基本割集中。
+最小支撑树T满足以下特征：
+**对于T中任意一条边e，e是由e决定的基本反圈中的最小权边。**
+**对于不在T中的任意一条边e，e是由e决定的基本圈中的最大权边。**
+=====Prim算法（反圈法）=====
+第一步：任取一个节点作为初始点。
+第二步：从已选点和未选点构成的反圈中，选择权最小的边。如果有多条边权最小，则任选其中一条。
+第三步：若在某一步，反圈为空集，则图中没有支撑树。若在某一步，已经选择了图的所有顶点，则所有被选择的边构成最小树，算法终止。
+因此可以用优先队列的STL来维护割集（反圈），方法是每次选元素后判断，新堆顶不在割集中就pop掉这个元素。
+注意，我们要实现最小堆。默认优先队列是最大堆。因此要想办法颠倒过来。
+<code C++>
+#include<algorithm>
+#include<iostream>
+#include<cstring>
+#include<stdio.h>
+#include<math.h>
+#include<string>
+#include<stdio.h>
+#include<queue>
+#include<stack>
+#include<map>
+#include<deque>
+using namespace std;
+struct edge//保存边的情况，to为通往的边，不需要保存from
+{
+    int to;
+    int v;
+    friend bool operator<(const edge& x,const edge& y)//优先队列即最小堆
+    {
+        return x.v>y.v;
+    }
+};
+priority_queue<edge>q;
+int vis[105];//判断是否标记数组
+int p[105][105];//存图
+int n;
+int main()
+{
+    int i,j,x,y,d2,d1,s,key;
+    edge now;
+    while(scanf("%d",&n)!=EOF)
+    {
+        for(i=0;i<n;i++)
+        {
+            vis[i]=0;//初始化一下
+            for(j=0;j<n;j++)
+            {
+                scanf("%d",&p[i][j]);
+            }
+        }
+        s=0;
+        vis[0]=1;//标记起始点
+        key=0;//随便找起始点
+        while(!q.empty())q.pop();
+        for(i=0;i<n-1;i++)//n-1次
+        {
+            for(j=0;j<n;j++)//记入新加入点的情况
+            {
+                if(!vis[j])//没标记过的点就加入全家桶套餐
+                {
+                    now.to=j;
+                    now.v=p[key][j];
+                    q.push(now);
+                }
+            }
+            while(!q.empty()&&vis[q.top().to])//最小边但是标记过就放弃
+            {
+                q.pop();
+            }
+            if(q.empty())
+                break;
+            now=q.top();
+            key=now.to;
+            s+=now.v;//累加最小边的和
+            vis[key]=1;
+            q.pop();
+        }
+        printf("%d\n",s);
+    }
+    return 0;
+}
+</code>
+<code C++>
+#include <iostream>
+#include <queue>
+#include <map>
+#include <cstring>
+using namespace std;
+#define maxint 0x3f3f3f3f
+#define maxnum 1051
+int link[maxnum][maxnum];
+int c[maxnum][maxnum];
+int sum,n;//sum为最小权之和，n为顶点个数
+struct node
+{
+	int s;//起点
+	int e;//终点
+	int w;//权
+};
+bool operator < (const node &a,const node &b)
+{
+	return a.w > b.w;
+}
+void prim(int s)
+{
+	int i,j,k,m,t,u,total;
+	int vis[maxnum];//标记访问
+	memset(vis,0,sizeof(vis));//初始化vis均为0，即未被访问
+	priority_queue <node> qq;//声明一个存储node结构体的优先队列
+	struct node nn;
+	total  = 1;
+	vis[s] = 1;
+	sum = 0;
+	while(total < n)//遍历所有的顶点
+	{
+		for(i=1;i<link[s][0];i++)//遍历所有和s点相连的边,s点为源点
+		{
+			if(!vis[link[s][i]])//若这个边没被访问，就将其加入优先队列
+			{
+				nn.s = s;
+				nn.e = link[s][i];
+				nn.w = c[s][nn.e];
+				qq.push(nn);
+			}
+		}
+        //这里就是简单处理一下特殊情况
+		while(!qq.empty() && vis[qq.top().e])//遇到顶点和集合外的顶点没有相连的
+			qq.pop();//刚巧这个点作为终点是最短的，因为这个顶点没背标记过，所以会错误的计入在内
+        //将优先队列的队顶元素输出
+		nn = qq.top();
+		s = nn.e;
+		sum += nn.w;//队顶的边就是最适合的边，因为优先队列的作用就是对权值进行排序，队顶总是
+                    //最大或最小的权值的边，又因为没被访问过，所有一定是最适合的
+		//cout<<nn.s<<" "<<nn.e<<" "<<nn.w<<endl;
+		vis[s] = 1;//标记为集合内的元素
+		qq.pop();
+		total++;//访问的点数加一
+	}
+}
+int main()
+{
+	int i,j,k;
+	int line,len;
+	int t,s,d,p,q;
+	cin>>n>>line;
+	for(i=1;i<=n;i++)
+	{
+		link[i][0] = 1;
+	}
+	for(i=1;i<=line;i++)
+	{
+		cin>>p>>q>>len;
+		c[p][q] = c[q][p] = len;
+		link[p][link[p][0]++] = q;
+		link[q][link[q][0]++] = p;
+	}
+	cin>>s;//输入起始点
+	prim(s);
+	cout<<sum<<endl;
+	return 0;
+}
+</code>
+=====Kruskal算法（避圈法）=====
+第一步：选取一个无圈支撑子图。初始时选择图的全体节点。
+第二步：若图连通，则它是最小支撑树。
+第三步：若图不连通，则选择边e，两个端点属于不同分支，并且权最小。重复上述过程。
+=====有趣结论=====
+在本文的最后，介绍一个与生成树（支撑树）有趣的结论：**如何编程判断一个图是不是二部图。**
+如果存在图G的一个支撑树T，使得所有的基本圈长都是偶数，那么G的所有圈长都是偶数，即G是二部图。
+当然，如果是二部图，所有圈长都会是偶数，因此随便一个生成树都可以判断，不一定最小。
+证明这个结论的关键，在于编程中常用的“异或”运算。
+异或运算的实质是，将并集中出现偶数次的元素去掉。为了叙述方便，简记每个节点度数都是偶数的子图为“偶度子图”。有以下显然结论：
+非空偶度子图一定有圈。
+偶度子图的异或还是偶度子图。
+不含奇长圈的图（二部图），异或也不含奇长圈。
+于是要证结论等价于：
+图G中任意一个圈可以写成基本圈的异或。
+这近乎于显然。图G中的圈C，必然有边不在支撑树T中，每一条这样的边都对应一个基本圈。这些基本圈的异或全体可以得到图C0。只要证明C0和C完全相同。
+由条件，C0是偶度子图。
+对于树T之外，圈C中的边，由基本圈的定义，这些边在C0中存在并且仅存在一次。
+对于树T之外，不在圈C中的边，显然也不会在选取的基本圈中，所以不在C0中。
+因此考虑C0和C的异或，得到的结果必然包含在树T之内。但是它们的异或是偶度子图，而树T当中没有圈，由于非空偶度子图一定有圈，只能说明C0和C的异或是空集。因此C0和C完全相同。

CVBB ACM Team

用户工具

站点工具

差别

页面工具