python最小生成树

Ⅰ Python 独立跳棋问题的算法思路是什么

这么好玩的算法。为什么不自己先试试呢。

你的问题里没有描述规则，所以我猜想，它应该是按跳棋的规则去跳，然后达到另外一个规则标准就会消除。

正常的做法，比较费时的做法是尝试每一种可能路径，通常是有深度的。比如尝试10步，或者是100步。然后评估结果。

不过可以通过自己的经验，让路径的选择变得简单。 减少规则推演的次数与深度。

这些都是最简单的逻辑。不过运畴学，还有一个什么什么科学是专门用来做这种棋路推演的。 你可以找教材书看一下。

或者是最简单的办法，找师兄师姐的论文看看。

如果是我自己做这种题目，我会采用“双向”推演，加上排除法，还有透视逻辑做。
另外为了提高效率，我会事先生成一个所有棋 路的最小生成树。这样可以减化“搬”动棋子的时间。

Ⅱ 三个月内如何突破noip

1.确定你的语言 NOIP接受Pascal、C、C++三种语言的参赛者，在学习的开始，务必确定自己使用的语言。 在中途变更自己学习的语言，对学习NOIP来说是非常大的困难。若是初学者，对C、C++没有基础，我个人建议学习Pascal。Pascal可读性高，对于初学者来说，比起C和C++，Pascal应该是更容易上手的。如果有较长时间的准备，不妨试试看学C或者C++，在以后的大学学习中也会有帮助，而且需要网上搜索题解时，C和C++的题解往往较多，更加方便阅读参考。 （本人使用Pascal语言，所以后文回答可能涉及到具体程序的大多是Pascal思维。）

2.从排序入手 排序是信息竞赛基础中的基础，值得我划出整整一块来为排序进行说明。 快速排序是必备本领，在信息竞赛中，若是不会快排，其他的知识就是空中阁楼，学习其他各种优化方法，排序却丢了时间，是万万不可的。学习快排最简单的方法是背。而C和C++应当是自带快排的，所以快速排序很是轻松。 而个人认为，快速排序以外，必须掌握的排序知识还有多关键字排序以及稳定的O(nlogn)排序。 多关键字排序来说，我个人是引入比较函数，在确定两个数字顺序时不单纯比大小，而使用函数处理判断先后。 而稳定排序，我学习了归并排序。它不仅是一个稳定排序，而且可以进行求逆序对等操作，对程序学习的帮助也非常大。

3.贪心和穷举以及模拟——最简单的程序 想要快速获奖，必须熟练掌握贪心和穷举以及模拟。它们虽然不能帮你得到满分，但是可以帮助你从得不到分变为得到30分甚至60分，或者说，它是你想不出更好算法时的救命稻草。 所谓贪心，就是通过局部最优来达成整体最优。每一步都获得当前能取得的最优值，最终也能获得最优值。虽然看似是非常正确的思路，但由于贪心算法所能够考虑因素往往具有局限性，得出的答案常常不会是最优解。但是，仍然需要强调的是，贪心在NOIP这一类比赛中，是能够得分的。 所谓穷举，就是列出所有可能的情况，然后从中寻找最优解。虽然看上去是非常简单的操作方法，但是实际应用时，通过穷举和剪枝（程序运行到一定程度由于能判断必定不是最优解而不再继续），可以达到意想不到的效果。 所谓模拟，常应用于给定步骤时。我们通过逐步进行操作、逐步判断来推断是否符合题目中所给出的情况。这种方法常常是非常耗费时间的，所以一般都不可能是最优解。但是，仍然是可以得到部分分数的一种简单而粗暴的方法。

4.用动态规划来训练思维 动态规划，我偶然跟母亲说到这个的时候，母亲想起了大学时的课程，然后一脸苦笑的样子现在都令我印象深刻（笑）。 动态规划是非常难的一个部分，虽然解题上有一定的规律，但是对于思维的周密程度和逻辑要求非常高。所以我会建议先通过动态规划来训练自己的思维。特别是在短时间内的学习的话，动态规划可以帮助你快速进入编程状态。并且，动态规划的思考也可能帮你发现题目背后可能隐藏的更简便的算法。 动态规划主要的思考规律应该是如下： 定义函数（动态转移方程中转移量的定义） 建立方程 确定初值和边界 由于没有具体的题目，我也不能详细说明动态规划。动态规划千变万化，题目类型多种多样，动态规划的种类也多种多样，难以一一赘述了。 需要提醒的是，在NOIP的考场上，千万不要因为想不到动态转移方程而放弃一道题目，尝试使用贪心等看似并不完全正确的做法来做，能够得到部分分数；也不要在动态规划写出后发现答案不正确后耗费太多的时间，经验表明要找出动态规划的错误点可能可以浪费你整场考试的时间。

5.学习简单的图论 我认为简单图论中包括的有：（单源或多源）最短路和（最小）生成树。 最短路中需要学习的有Dijkstra算法和Floyd算法。Dijkstra算法有点像图论中的动态规划，而Floyd则是图论中的穷举法。但是由于近年来图论的题目越来越困难，加入的其他知识越来越多，没有长时间准备的话，这两种算法掌握即可。如果想再深入一点的话，可以学习SPFA，SPFA也是非常实用的一种算法。 最小生成树就不得不提Prim算法和Kruskal算法。最小生成树的算法中，这两种某种意义上都可以算是贪心的算法。Prim算法更适用于稠密图，而Kruskal算法更适用于稀疏图。如果要学习最小生成树的话，两者都学习并且对比是一种很好的方法，能够看到两种算法的优点和不足。

6.常用的数据结构——让程序更快一点 数据结构中想说的NOIP常常能够用到的是：堆（优先队列）、并查集。更加深入学习还可以提到树状数组 堆，这种数据结构只关注“直系亲属”之间的关系，而不关注“旁系”。常常能够配合贪心使用。例如NOIP的经典题合并果子，虽然能够想出是贪心，但是如果不明白堆的话，程序也不能够得到满分。 并查集，能够快速判断两个元素是否有关联，增加了其他手法之后还能够判断元素之间关系。比如说上面提到的Kruskal，一种非常常见的写法中就运用到了并查集来判断两个点是否已经被连接。 树状数组，能够查询和修改操作复杂度比较平衡的一种算法，正因如此常用来解决同时需要查询和修改的问题。

7.不知道该放在哪里说的搜索——和枚举很像 老师每次被要求讲解搜索都会非常无奈，因为每次讲解完搜索，同学们都会以一种“啊，原来是这样”的眼神看着他，而几个月后还会再重复这样的场景（笑）。 搜索大题来说分为深度优先搜索和广度优先搜索。深度优先搜索就是一条路走到死，撞墙了再回头，而广度优先搜索则是每一步就将下一步所有的可能性放入队列中，然后按照队列顺序来探测。 初赛经常会考深度优先遍历或广度优先遍历后是什么顺序，而复赛的搜索题会加入许多复杂的因素，所以也请好好学习一下这一部分。

8.最后的最后，一定要学习的数学基础知识 简单列举一下： 快速幂 高精度 筛法选素数 扩展欧几里得定理（辗转相除法） 这些在考前一定要重新再看一遍，因为难度并不大但是NOIP考到的几率并不小（会隐藏在第一题中）。

Ⅲ Python中prim算法或kruscal算法的实现

kruskal:
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define MAXE 100 //MAXE为最大的边数
struct edges
{
int bv,tv,w; //边集类型,存储一条边的起始顶点bv、终止顶点tv和权w
}edges;
typedef struct edges edgeset[MAXE];
//寻找v所在的连通集
int seeks(int set[],int v)
{
int i=v;
while (set[i]>0)

i=set[i];
return i;
}
void kruskal(edgeset ge,int n,int e)
{
int set[MAXE],v1,v2,i,j;
for(i=1;i<=n;i++)
set[i]=0;
i=1; //i表示待获取的生成树中的边数,初值为1
j=1; //j表示ge中的下标,初值为1
while(j<n&&i<=e)//按边权递增顺序,逐边检查该边是否应加入到生成树中
{
v1=seeks(set,ge[i].bv); //确定顶点v所在的连通集
v2=seeks(set,ge[i].tv);
cout<<ge[i].bv<<":"<<v1<<", "<<ge[i].tv<<":"<<v2<<endl;
if(v1!=v2) //当v1,v2不在同一顶点集合,确定该边应当选入生成树
{
cout<<"("<<ge[i].bv<<", "<<ge[i].tv<<") "<<ge[i].w<<endl;
set[v1]=v2;
j++;
}
i++;
}
}
int main()
{
edgeset ee;
int n,e; //n是图的结点数,e是图的边数
n=6;
e=3;
for(int i=1;i<=e;i++)
{
scanf_s("%d",&ee[i].bv);
scanf_s("%d",&ee[i].tv);
scanf_s("%d",&ee[i].w);
}
//ee表示的边集图是按权值从小到大排列的
printf("最小生成树边集及它的权值: \n");
kruskal(ee,n,e);
system("pause");
return 0;
}
prim:

#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define N 3
void prim(int c[N][N])
{
//lowcost 为顶点间的最小距离，closest为最小距离上的邻接顶点
//lowcost[i]:与顶点i连通的最小边的权值
//closest[i]:与顶点i连通的邻接顶点
int lowcost[N],closest[N];
int i,j,k,min;

//lowcost,closest初始化
for(i=0;i<N;i++)
{
lowcost[i]=c[0][i];
closest[i]=0;
}
closest[0]=-1;

//寻找U 和 V 之间连接的最短距离的邻接点
for(i=0;i<N;i++)
{
min=32767;
k=0;
//寻找U 和 V 之间连接的最短距离的邻接点
for(j=0;j<N;j++)
{
if((lowcost[j]<min)&&(closest[j]!=-1))
{
min=lowcost[j];
k=j;
}
}
//输出新的邻接顶点，并修改lowcost值
if(k)
{
cout<<"("<<closest[k]<<", "<<k<<") "<<lowcost[k]<<endl;
closest[k]=-1;
for(j=1;j<N;j++)
{
if(closest[j]!=-1)// huo if(!(closest[j]==-1))
{
//修改lowcost值
lowcost[j]=c[k][j];
//修改邻接顶点
closest[j]=k;
}
}
}
}
}

int main()
{
int i,j,a[3][3];
cout<<"请输入二维数组："<<endl;
for(i=0;i<3;i++)

for(j=0;j<3;j++)

cin>>a[i][j];
cout<<"最小树的结构为："<<endl;
prim(a);
int q;
cin>>q;
return 0;
}