最小生成树的胡思乱想–做减法
今天看到最小生成树的算法
忽然想到 为什么现在的做法都是在 做加法呢？
为什么不尝试一下减法呢？
比如说我们的顶点数n，边数m n和m相差不多。
如果我们做加法的话要做 n-1条，假如说n比较大
但是我们如果**做减法，
应该只需要 （ m-（n-1） ）条**，
因为前提已经有 （m-n）是一个很小的可以接受的数了，
所以我们可以得出 做减法 需要减去的条数
是会远远小于 做加法 需要加起来的条数的
两者的目的最终都是为了生成最小生成树
就当是我瞎想了，看看能不能证明。
好吧，下面就先记录一下自己不太成熟的算法：
开始需要明确一点，就是最小生成树是针对无向图来说的。
首先，
n为顶点数，m为边数
定义一个G[MAXV][MAXV]，将每条边的边权存放进来。
其中，MAXV是最大顶点数。例如：const int MAXV=510;
定义一个int inq[MAXV]={0}，标记数组，初始值为0，标记图中的 各个顶点
分别被集合s中si条边包含，则对应的inq[i] = si;
判断是否满足生成树，也就是加入集合s中的边是否将所有的点都包含了进来。
什么时候生成树一定不满足呢？
就是inq数组中1~n 或者是0~n-1编号的n个
顶点有任意一个 inq[i]=0;
这种情况就一定不满足了。
先说一种粗略的，以后再想能不能剪枝。
首先接收外部数据u,v,w。分别是每条边的两个顶点及边权
因为是无向图，而且其实，这个算法考虑了 u->v 了，就
不用重复考虑 v->u 这个地方可以省一点空间和时间。
//定义无穷大
const int INF=0x3fffffff;
scanf("%d%d",&n,&m);
//**此处是以编号0~n-1 为例**
//**初始时默认不可达**
fill(G[0],G[0]+MAXV*MAXV,INF);
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
G[u][v]=w; //如果上面的节省步骤实现，就不用保留其中一个了
inq[u]+=1; //如果上面的节省步骤实现，这里也会修改
inq[v]+=1;
//而且要记得是累加！！！
}
//以上工作全是属于初始化工作
//以下是算法阶段
首先我想说一下特殊情况，就是
初始化工作完成之后，inq[]数组中 0~n-1 仍然有 0 值元素
也就是本身提供的图G不足以达到生成最小生成树的条件，此时
也就根本没有必要 去 生成最小生成树，直接退出。
//其实我一直在想是不是还有什么更好的容器来替代inq数组
//set? map? priority_queue? queue? stack? vector?
bool is_tree=true;
for(int i=0;i<n;i++)
{
if(inq[i]==0)
{
is_tree=false;
break;
}
}
if(!is_tree)
{
printf("无法生成最小生成树！！");
return;
}
//以上其实还可以加一个判断，以上的处理其实是针对m>n的时候的处理
//还可以加下面的判断，有点多此一举，但是下面的判断在某些情况下
//省下了遍历的阶段，可以直接退出。
/*
if(m<n-1 )
{
printf("无法生成最小生成树！！");
return;
}
*/
//如果可以生成最小生成树，则继续下面的算法
int now_edge=m;
//做减法，要求就是谁大减谁，哪条边大减谁
//但是这里也是可以剪枝的，就是如果减去这条边的话，
//对应的与其相连的点会出现 inq[u]==0 || inq[v] == 0 的情况，
//也就是没剪之前 出现 inq[u]==1 || inq[v] == 1 这样的话
//这条边就不可以减 ，继续寻找下一个较大的边。。。直到找到。或者now_edge==n-1时为止
//自动排序的话，或许之后可以考虑用到优先队列priority_queue
while(now_edge!=n-1)
{
//以下就是筛选最大元素的过程，或许还能进化
int u=-1,v=-1,MAX=-1;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if( inq[i]>1 && inq[j]>1 && MAX< G[i][j] )
{
u=i;
v=j;
MAX=G[i][j];
}
}
}
G[u][v]=INF;
now_edge--;
inq[u]--;
inq[v]--;
}
//这里其实应该已经得出最后的最小生成树了
//由于是刚冒出的想法，可能还有地方存在漏洞，需要验证。
京公网安备 11010502036488号