软件综合实习报告
软件综合实习报告
题目:最小生成树算法
院(系):
计算机学院
专
业:
计算机科学与技术
姓
名:
班级学号:
2012 年 9 月 12 日
目录 一 . 系统需求分析与总体设计
............................................................................ 1
1.1 需求分析 ……………………………………………………………………………………………………………… 1
1.1.1 问题描述…………………………………………………………………………………………………………1
1.1.2 问题分析…………………………………………………………………………………………………………1
1.1.3 方案选择…………………………………………………………………………………………………………1
1.1.4 开发平台…………………………………………………………………………………………………………2
1.2 系统总体设计 ……………………………………………………………………………………………………. 2
二 . 详细设计与系统实现
....................................................................................... 2
2.1 Prime 算法动态演示模 ……. ……………….……………………………………………………………. 2
2.1.1 基本思想…………………………………………………………………………………………………………2
2.1.2 设计与实现……………………………………………………………………………………………………..3
2.2
Kruskal 算法动态演示模块 ………………………………………………………………………. 4
2.2.1 基本思想…………………………………………………………………………………………………………4
2.2.2 设计与实现………………………………………………………………………………………………………4
2.3
并查集实现 kruskal 算法动态演示模块 ……………………………………………….. 4
2.3.1 基本思想…………………………………………………………………………………………………………5
2.3.2 设计与实现………………………………………………………………………………………………………5
2.4 深 度优先搜索实现 Kruskal 算法动态 演示模块 ………………………………. 6
2.4.1 基本思想…………………………………………………………………………………………………………6
2.4.2 设计与实现………………………………………………………………………………………………………7
2.5
广度优先搜索实现 Kruskal 算法动态演示模块 ………………………………. 7
2.5.1 基本思想…………………………………………………………………………………………………………7
2.5.2 设计与实现………………………………………………………………………………………………………8
2.6 画图模块 ……………………………………………………………………………………………………………….. 8
三 .系统测试
.................................................................................................................. 9
3.1 测试数据 ……………………………………………………………………………… 9
3.2Primme 的测试结果 ………………………………………….…………………… 9
3.2Kruskal 算法的测试结果 ………………………………………….………..…. 10
3.3 并查集实现Kruskal 算法的测试结果 ……………………………………. 10
3.4 深度优先搜索实现Kruskal 算法的测试结果 …………………………. 11
3.5 广度优先搜索实现Kruskal 算法的测试结果 …………………………. 11
3.6 效率分析 ……………………………………………………………………………. 12
四 . 总结
........................................................................................................................... 12
参考资料 ……………………………………………………………………………………………………………………. 13
一. 系统需求分析与总体设计 1 1.1 需求分析
1.1.1 问题描述 在一个具有几个顶点的连通图 G 中,如果存在子图 G" 包含 G 中所有顶点和一部分边,且不形成回路,则称 G" 为图 G 的生成树,代价最小生成树则称为最小生成树(Minimal Spanning Tree)。
许多应用问题都是一个求无向连通图的最小生成树问题。例如:要在 n 个城市之间铺设光缆,主要目标是要使这 n 个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同;另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
基本的要求是实现两种算法:通过实现Kruskal算法和Prim算法来得到图的最小生成树。并对两种算法进行分析和比较。较高的要求是在边通分量的查询与合并的过程中,采用广度优先搜索算法(Breadth First Search)、深度优先搜索算法(Depth First Search)和并查集(Union-Find Set)这三种方法,并进行分析和比较算法时间复杂度。
测试数据如下:
图(1)
1.1.2 问题分析 通过问题的描述,可知这一道题目主要涉及,面向对象的分析与设计,数据结构和算法。通过这些利用知识实现 Kruskal 算法和 Prim 算法从而得到图的最小生成树。除此之外,在最小生成树的求解过程中会对边通分量进行查询和合并,由题可知要对边通分量进行查询和合并要使用广度优先搜索算法(Breadth First Search)、深度优先搜索算法(Depth First Search)和并查集(Union-Find Set)这三种方法。
为了更好、更生动的表示这些算法的运算过程,在这里如果使用动态显示算法的求解过程将会是最好的选择。对于不同的算法其求解最小生成树时运算的效率是不同的,因此还需要对各种算法时间复杂度进行分析和比较,从而更加深入的理解算法,从而方便我们在不同的场合采用不同的实现算法。
1.1.3 方案选择 通过对题目的分析,对于如何将广度优先搜索算法(Breadth First Search)、深度优先搜132 5 4 6 5 6 5 2 4 4 7
3 1 7 1
索算法(Depth First Search)和并查集(Union-Find Set)这三种方法运用到对边通分量进行查询和合并中有不同的结合方法。在这里我选择了将这三种搜索算法融合到 Kruskal 算法,因为我觉得在 Kruskal 算法对边通分量进行查询和合并中使用这三种方法更合理且更容易实现,因此也实现了将这三种搜索算法融合到 Kruskal 算法从而实现对图的最小生成树的查找。
对于运用图形学的知识实现算法的动态运行效果。可以知道使用 MFC 通过单文档画图来实现算法动态显示运行效果或者使用对话框来实现算法动态显示运行效果,为了方便起见,我选择的是通过 MFC 建立单文档来实现这一效果。
1.1.4 开发平台 使用的系统是 Windows07 , 开发工具 VC++6.0 2 1.2 系统总体设计
由于这是对图进行相关的操作,因此涉及图的存储问题,在这里使用的是邻接矩阵这一数据结构来实现图的存储。在对图进行相关操作寻找最小生成树时,得到的生成树中的边采用的是结构体的存储方式,在实现的过程中相关变量和数据的存储也主要通过数组、结构体来实现了。
在深度优先搜索算法(Breadth First Search)中使用了栈这一数据结构来实现边的连通分量的查询,对广度优先搜索算法(Depth First Search)的实现使用了队列这一数据结构,这里的队列和栈都是通过编程实现。
这里主要分为六个模块,即 prime 算法模块、kruskal 算法模块、用并查集实现 kruskal算法的模块、kruskal 算法和深度优先搜索算法结合的模块、kruskal 算法和广度优先搜索算法结合的模块以及画图操作的相关模块。设计与实现中由于所体现的重点不同,因此下面的说明主要围绕着此题的重点,即最小生成树的生成过程。
对于最小生成树生成过程中边相关变量的存储均是通过定义一个边(edge)的结构体变量进行存储的,而关于点的存储则是通过定义数组进行相应的存储,由于不同的实现方法采用的初始值不一样,因此使用的数组会有所不同。
对于算法运行时的动态显示运行过程这一要求主要通过将相关的画圆、画线等相关画图的操作扦插到相关的算法中,在算法的运行过程中再通过对相关条件的判断从而决定是否执行画圆、画线等操作。在这些算法运行过程中实现的画图操作主要通过调用一个公用的函数进行画图的相关操作。
二. 详细设计与实现 e 2.1 Prime 算法动态演示模块
2.1.1 基本思想
Prime 算法的基本思想是以图中的某一个顶点作为起始顶点,然后从起始顶点出发不断 的从还没有遍历到的顶点中选择与已经遍历到的顶点存在之间权值最小边的顶点,并将新遍历的点不断的添加到已经遍历的顶点集合中。通过这样的一个遍历过程与画图的相关操作结合来实现最小生成树生成过程的动态演示。
对于无向连通图 G(V,E),在 prime 算法中,将图 G 顶点集合分为两个集合 V1(G)和V2(G),V1(G)用来存储当前已经遍历到的顶点,即最小生成树中的顶点 V(MST),V2(G)
用来存储还没有遍历到的顶点。对于已经选择的顶点之间的边存储在最小生成树的边的集合中 E(MST)。
Prime 算法的具体过程如下:
设最小生成树中点的集合 V(MST)和边的集合 E(MST)的初态均为空。首先从图 G 的顶点 集 V(G)中任选一个顶点,把它加到最小生成树 MST 的顶点集 V(MST)中。然后,依次选出 n-1条符合以下条件的边(vi,vj)。
(1)(vi,vj)E(G),v 是 V(MST)的顶点,而 vj 是还未加入 V(MST)的顶点。此时(vi,vj) 一定均未加入 E(MST)。通过判断先找出所有这样的边 。
(2)(vi,vj)是关联于 V(MST)中顶点的边中权值最小的边。选出满足该条件的边,将
vj 加入 V(MST),(vi,vj)加入 E(MST) ,之后画出相应的边和新添加进去的顶点。
下面主要通过题目中给出的例子(如图 1)对 prime 算法进行详细的解析:
(1)将 1 作为起始顶点添加到 V(MST),找到与之相连的符合条件的边(v1,v2),将权值为 5 的边添加到 E(MST)中,并将顶点 2 添加到 V(MST)中并画出此边。
(2)集合 V(MST)此时已经有两个顶点了,即 1、2,找到与之相连的符合条件的边(v2,v3) 将权值为 1 的边添加到 E(MST)中,并将顶点 3 添加到 V(MST)中并画出此边。
(3)集合 V(MST)此时已经有三个顶点了,即 1、2、3,找到与之相连的符合条件的边(v2,v4)将权值为 2 的边添加到 E(MST)中,并将顶点 4 添加到 V(MST)中并画出此边。
(4)集合 V(MST)此时已经有四个顶点了,即 1、2、3、4,找到与之相连的符合条件的边(v4,v5)将权值为 3 的边添加到 E(MST)中,并将顶点 5 添加到 V(MST)中并画出此边。
(5)集合 V(MST)此时已经有五个顶点了,即 1、2、3、4、5,找到与之相连的符合条件的边(v4,v6)将权值为 4 的边添加到 E(MST)中,并将顶点 6 添加到 V(MST)中并画出此边。
(6)集合 V(MST)此时已经有六个顶点了,即 1、2、3、4、5、6,找到与之相连的符合条件的边(v6,v7)将权值为1的边添加到E(MST)中,并将顶点7添加到V(MST)中并画出此边。
至此图 G 中所有的点均已添加到了 V(MST),最小生成树生成完毕,其权值为 16。
2.1.2 设计与实现 对于 prime 算法的动态演示,主要是关乎两个函数的实现一个是画图函数的实现,另 外一个就是如何判断何时进行画图操作并进行相关操作的画图函数,在这里主要通过两个函数实现一个是与 Kruskal 算法动态实现的公用的画图操作函数,另外一个就是 prime 算法寻找最小生成树的实现。这里仅给出语言描述的实现过程,源代码的实现在后面的附录中将会给出。
Prime 算法的设计与实现 如下所述:
(1)对所画区域刷新。
(2)
MST 顶点初始值={序号为 0 的顶点},其边所在的结构体数组 E[n-1]的值也为空。lowCost的初始值为邻接矩阵中第0行的值,这样初始时lowCost中就存放了从集合V(MST)中顶点 0 到集合 V(G)-V(MST)中各个顶点的权值 。
(3)循环 n-1 次 2.1 从 lowCost 中寻找具有最小权值的边。根据 lowCost 的定义,这样的边其一个顶点必然为集合 V(MST)中的顶点,其另一个顶点(设第 k 个顶点)必然为集合 V(G)-V(MST)中的顶点 ,将相应的边添加到 E[n-1]中。
2.2 存第 k 个顶点的数据和相应边的权值到 MST 中,并将 lowCost[k]置为-1,表示第k 个顶点从集合 V(G)-V(MST)加入了集合 V(MST)中
2.3 当第 k 个顶点加入到集合 V(MST)后,若存在一条边(k,j),其中 k 是集合 V(MST)的顶点,j 是集合 V(G)-V(MST)的顶点,且边(k,j)权值较原先 lowCost[j]的代价更小,则用这个权值修正原先 lowCost[j]中的权值。
2.4 当最小生成树生成完毕时,则调用 Draw(E)函数画出生成的过程。
l 2.2 Kruskal 算法动态演示模块
2.2.1 基本思想 Kruskal 算法通常是在已知 V(MST)=V(G),E(MST)的初态为空时对图 G 进行相关处理的到最小生成树的。首先将图中所有边按权值递增顺序排列,依次选定取权值较小的边,但要求后面选取的边不能与前面选取的边构成回路,若构成回路,则放弃该条边,再去选后面权值较大的边。每次挑选边成功了即画出此边。在 n 个顶点的图中,选够 n-1 条边即可。具体如下:
(1)
构造一个只有 n 个顶点没有边的非连通图 T,图中的每个顶点为一个连通分量。
(2)
在原图 G 中的边中选择具有最小权值的边,若该边的两个顶点落在不同的连 通分量上,则将此边加入到 T 中;否则,则将此边舍去(此后永不选入此边),重新选择一条权值最小的边并进行画图的操作处理。
(3)如此反复下去,直到所有顶点在同一个连通分量上为止。
下面主要通过题目中给出的例子(如图 1)对 kruskal 算法进行详细的解析:
(1)在图 G 的边的集合 E 中按存储次序选择权值最小的边,即(2,3)由于边(2,3)在(6,7)前面存储,所以此处选择的边(2,3)并画出此边,其权重为 1。
(2)在图 G 的边的集合 E 中按存储次序选择权值最小的边,即(6,7)由于边(6,7)在(2,3)后面存储,所以后选择边(6,7)并画出此边,其权重为 1。
(3)在图 G 的边的集合 E 中选择权值最小的边(2,4)并画出此边,其权重为 2。
(4)在图 G 的边的集合 E 中选择权值最小的边(4,5)并画出此边,其权重为 3。
(5)在图 G 的边的集合 E 中选择权值最小的边(4,6)并画出此边,其权重为 4。
(6)在图 G 的边的集合 E 中选择权值最小的边(1,2)并画出此边,其权重为 5。
至此通过 kruskal 算法得到最小生成树及生成过程,其最小生成树的权值为 16。
2.2.1 模块设计与实现 Kruskal 算法的实现主要包含两个部分,即带权值的边的排序和判断选取的边的两个顶点是否属于同一个连通分量。因此首先将图 G 的顶点集合 V 分为 n 个等价类,每个等价类包括一个顶点;然后以权值的大小为顺序处理各条边,如果某条边连接两个不同等价类的顶点,则这条边被添加到 MST(选取的边不与前面选取的边构成回路),两个等价类被合并为一个;反复执行此过程,直到只剩下一个等价类。
kruskal 算法的设计与实现如下所述(具体的代码实现见附录):
(1)对所画区域进行刷新。
(2)设置查找到的顶点集合 find[n]所有的值为-1,存储边的集合 E[n-1]为空集。
(3)判断找到的边的数目是否小于顶点的数目减一,即 n-1,如果是则从没有被选中的边中选取权值最小的边,如果放入存储边的集合中不构成回路则添加进去,否则舍去此边。
(4)如果不符合(2)中的判断则不断的重复直到选取的边等于 n-1。
(5)当最小生成树生成完毕时,则调用 Draw(E)函数画出生成的过程。
3 2.3 并查集实现 l kruskal 算法动态演示模块
2.3.1 基本思想 并查集处理问题的主要思想是在处理时使用搜索与合并运算对相关集合进行处理。最初 把每一个对象看做是一个单元集合,然后依次按顺序读入一个等价对后,将等价对中的两个元素所在的集合合并。在此过程中不断的重复使用一个搜索运算,从而确定此元素在哪一个集合中,当读入一个等价对 A≡B 时,首先检测 A 和 B 是不是属于同一个集合,如果是,则不用合并;如果不是,则使用一个合并运算把 A 和 B 合并到同一个集合中,使得这两个集合中的任意两个元素都是等价的(依据等价的传递性)。
在此处实现 Kruskal 算法时主要使用并查集对相关顶点进行搜索和合并,从而实现了使用并查集实现 Kruskal 算法。在程序中也实现了并查集的动态演示,通过 Kruskal 算法调用并查集的函数,在函数中 对相关的顶点信息进行判断从而实施相应的画图操作。
下面通过题目的例子(如图 1)对 kruskal 算法利用并查集实现过程中相应集合的变化进行了详细的解析:
(1)最初的集合有 7 个,这 7 个集合中均只有一个元素分别为{1}、{2}、{3}、{4}、{5}、{6}、{7}。画出初始状态。
(2)在图 G 的边的集合 E 中按存储次序选择权值最小的边,即(2,3)由于边(2,3)在(6,7)前面存储,所以此处选择的边(2,3)其权重为 1。此时集合变为{1}、{2、3}、{4}、 {5}、{6}、{7}。通过判断画出发生改变的集合{2、3}。
(3)在图 G 的边的集合 E 中按存储次序选择权值最小的边,即(6,7)由于边(6,7)在(2,3)后面存储,所以后选择边(6,7),其权重为 1。此时集合变为{1}、{2、3}、{4}、 {5}、{6、7}。通过判断画出发生改变的集合{6、7}。
(4)在图 G 的边的集合 E 中选择权值最小的边(2,4)并画出此边,其权重为 2。此时集合变为{1}、{2、3、4}、{5}、{6、7}。通过判断画出发生改变的集合{2、3、4}。
(5)在图 G 的边的集合 E 中选择权值最小的边(4,5)并画出此边,其权重为 3。此时集合变为{1}、{2、3、4、5}、{6、7}。通过判断画出发生改变的集合{2、3、4、5}。
(6)在图 G 的边的集合 E 中选择权值最小的边(4,6)并画出此边,其权重为 4。此时集合变为{1}、{2、3、4、5、6、7}。通过判断画出发生改变的集合{2、3、4、5、6、7}。
(7)在图 G 的边的集合 E 中选择权值最小的边(1,2)并画出此边,其权重为 5。此时集合变为{1、2、3、4、5、6、7}。通过判断画出发生改变的集合{1、2、3、4、5、6、7}。
至此 kruskal 算法利用并查集查找、合并的过程结束,通过 kruskal 算法得到最小生成树及生成过程,其最小生成树的权值为 16。
2.3.2 设计与实现 Kruskal 算法利用并查集实现查找、合并的设计与实现也是首先选择权值最小的边,其次是利用并查集来对所要选择的那些顶点进行查找、合并。在 Kruskal 使用并查集时首先对其进行边集合的排序,接着利用并查集对图 G 中的顶点进行初始化,每一个顶点当做一个集合,同时给其一个相关的变量标志其集合中顶点的数目;然后利用并查集判断此时的顶点所在集合是不是相同,如果不相同则合并这两个顶点所在的集合。
并查集的实现主要包含三个方面,即并查集的初始化、查找和集合的合并,下面主要介绍并查集这三个过程的设计与实现。
(1)对所画区域进行刷新。
(2)初始化过程:为了方便并查集的描述与实现,通常把先后加入到一个集合中的元素表示成一个树形结构,并用根节点来代表这个集合。这里定义一个 parent[n]的数组,parent[i]中存储的就是结点 i 所在的树中的结点 i 父亲结点的序号,并查集的初始化中所有的
结点的 parent 值均为-1,即每个结点就是根节点,只包含它本身这一个元素。
(3)查找:主要是查找并返回结点 i 所属集合的根节点。在此函数中如果只靠一个循环来得到结果,则对于合并中得到的层次比较深的集合,查找会很费时。这里通过压缩路径的方法来加快后续的查找速度,主要是通过增加一个 while 循环,每次都把从结点 i 到集合根节点的路径上经过的结点直接设置为根结点的子结点。
(4)合并:两个集合合并时,任何一方均可作为另一方的子孙。在这里采用的是加权合并,即把两个集合中元素个数少的根结点作为元素个数多的根节点的子结点。这样处理可以减少树中深层次元素的个数,减少后续查找时间。在每一次的合并过程结束时,将会画出合并之后的集合。
2.4 深度优先搜索实现 l Kruskal 算法动态演示模块
2.4.1 基本思想 深度优先搜索主要是在图的遍历中使用此方法对整个图进行遍历来访问整个图中所有节点的一种遍历方法。通常是利用递归来实现图中结点的遍历。其基本思想是:对于一个无向连通图,从某一个起始结点 vi 出发,访问与它相连的一个结点 vj,且 vi、vj 这两个结点之间的边(vi、vj)是所有以 vi 为连接结点的边中权值最小的;然后再从 vj 出发寻找与 vj 相连的顶点,且它们之间的边是所有以 vi 为连接结点的边中权值最小的,不断的重复直到找到访问完所有的结点为止。
在这个算法的实现过程中,边通分量的查找虽然是深度优先搜索为主,但是是以最小生成树的的生成过程为主,因此这里所采用的画图操做运行的情况和使用一般的方法实现kruskal 算法的运行过程是一样的,在这里不再给予详细的说明,如有必要则可以参照 kruskal的生成最小生成树的过程。对于深度优先搜索方法的实现这里使用的方法是通过利用栈这一数据结构来实现的。下面仅给出在边已经通过权值大小进行排序之后,边通分量的查找的过程和查找之后集合的合并情况 (1)得到图 G 中最小权值的边(2,3),因为(2,3)排在(6,7)的前面,所以先判断它的两个结点,判断点 2 和点 3 是否已经访问过了,由于数组 check 中相应的值为 0,说明没有被访问过,因此合并这两个结点为一个集合{2、3}。同时通过深度优先搜索对这两个结点分别进行判断及标记已经访问过了。
(2)继续向下查找得到边(6,7),判断点 6 和点 7 是否已经访问过了,由于数组 check中相应的值为 0,因此合并这两个结点,得到新的集合{6、7}。同时通过深度优先搜索对这两个结点分别进行判断及标记已经访问过了。
(3)继续向下查找得到边(2,4),判断点 2 和点 4 是否已经访问过了得知点 2 已经被访问过了,点 4 没有,因此得到新的集合{2,、3、4}。同时通过深度优先搜索对着两个结点分别进行判断是否需要标记,可知点 4 此时被标记访问过了。
(4)继续向下查找得到边(4,5),判断点 4 和点 5 是否已经访问过了得知点 4 已经被访问过了,点 5 没有,因此得到新的集合{2,、3、4、5}。同时通过深度优先搜索对着两个结点分别进行判断是否需要标记,可知点 5 此时被标记访问过了。
(5)继续向下查找得到边(4,6),判断点 4 和点 6 是否已经访问过了得知点 4 已经被访问过了,点 6 没有,因此得到新的集合{2,、3、4、5、6、7}。同时通过深度优先搜索对着两个结点分别进行判断是否需要标记则知均不需要。
(6)继续向下查找得到边(5,6),判断点 5 和点 6 是否已经访问过了得知已经被访问过了,因此得到不进行集合的合并,继续向下查找相应的边。
(7)继续向下查找得到边(1,2),判断点 1 和点 2 是否已经访问过了得知点 2 已经被
访问过了,点 1 没有,因此得到新的集合{1、2,、3、4、5、6、7}。同时通过深度优先搜索对着两个结点分别进行判断是否需要标记,可知点 1 此时被标记访问过了。
至此通过利用深度优先搜索进行边通分量查询的 kruskal 算法运行完毕,通过对比可知和使用普通的查找算法得到的运行结果是一致的。
2.4.2 设计与实现 在这里采用 Kruskal 算法得到最小生成树的过程中,在对边连通分量的查询时使用了深度优先搜索的方法来查询当前得到的具有最下权值的边的两个顶点是不是已经存在于被访问过的结点的集合中,如果是的则进行下一次查询,否则的话则将没有访问过的结点加入已经访问过的结点的集合中。
深度优先搜索的实现主要利用栈这一数据结构来实现。因此主要包含两个方面,即栈这一数据结构中相关函数的设计与实现,以及如何实现深度优先搜索算法判断变量通分量的设计与实现。由于对栈已经比较熟悉,在这里仅作简要的说明。
(1)栈:
这里使用到的与栈相关的操作主要有栈中数据的初始化 StackInitiate、将数据压入栈的操作 StackPush、将数据弹出栈的操作 StackPop、判断栈是否为空的操作StackNotEmpty 和得到栈顶元素的操作 StackTop。
(2)查找与合并:在深度优先搜索中首先判断是否需要标记此节点,如果需要标记此节点则将此节点标记为以访问过,并添加到已经访问过的结点的集合中,并将相应的边存入E[]中;如果是要进行判断两个结点是不是都已经访问过了,及是否属于同一个集合利用栈来不断的搜索其中一个结点所在的集合中是否有另一个结点,如果存在则舍弃当前所选择的边,否则选择此边为最小生成树的一边。
下面给出 kruakal 算法利用深度优先搜索进行边连通分量查询和合并从而得到最小生成树的的设计与实现步骤:
(1)对所画区域进行刷新。
(2)对已经排好序的边进行选择,对没有访问过的最小权值的边的两个结点进行判断,检查是否已经被访问过了,如果有一个没有被访问过,则将和此边相应的顶点进行深度优先搜索的判断之后进行标记,同时存储所选择的这个边和相应的顶点。
(3)如果都已经被访问过了,则利用深度优先搜索判断这两个节点是否属于同一个集合,如果是的话则抛弃此边,如果不是的话则对其进行标记,并画出此边和相对应的点。
(4)选择下一条没有被访问过的边重新进行(1)、(2)的判断,直到所有的顶点均已被访问过且在同一个集合中,即已经添加到了最小生成树中则最小生成树生成完毕。
(5)当最小生成树生成完毕时,则调用 Draw(E)函数画出生成的过程。
2.5 广度优先搜索实现 l Kruskal 算法动态演示模块
2.5.1 基本思想 广度优先搜索主要是在图的遍历中使用此方法对整个图进行遍历来访问整个图中所有节点的一种遍历方法。通常是利用队列这一数据结构来实现图中结点的遍历。其基本思想是:对于一个无向连通图,从某一个起始结点 vi 出发,依次访问与它相连的所有未访问过的结点 vj1、vj2……vjn,然后在顺序访问 vj1、vj2……vjn 的所有还未访问过的邻接顶点;再从这些邻接顶点出发,再访问它们的所有未访问过的邻接顶点,……,不断重复直到图 G 中所有的顶点都被访问过为止。
kruskal 算法利用广度优先搜索进行边通分量的查询和合并的的实现过程中,边通分量的查找和合并虽然是广度优先搜索为主,但是总体是以最小生成树的的生成过程为主,因此
这里所采用的画图操做运行的情况和使用一般的方法实现 kruskal 算法的运行过程是一样的,在这里不再给予详细的说明,如有必要则可以参照 kruskal 的生成最小生成树的过程。对于广度优先搜索方法的实现这里使用的方法是通过利用队列这一数据结构来实现的。
这里采用的广度优先搜索主要是用来检索边的邻接顶点是不是在同一个集合中,由于使用 kruskal 算法时最初已经对边进行了一个排序,所以每一次所选用的边和通过广度优先搜索对邻接顶点进行判断的结果是一样的,在这里不再给予详细的说明,kruskal 算法结合广度优先搜索具体的运算过程和 kruskal 算法结合深度优先搜索的运算过程是一样的,在这里不再列出。由于本题的重点是最小生成树的生成,在这里不再给出广度优先搜索具体的搜索过程。
2.5.2 设计与实现 在这里采用 Kruskal 算法得到最小生成树的过程中,在对边连通分量的查询时使用了广度优先搜索的方法来查询当前得到的具有最下权值的边的两个顶点是不是已经存在于被访问过的结点的集合中,如果是的则进行下一次查询,否则的话则将没有访问过的结点加入已经访问过的结点的集合中。
广度优先搜索的实现主要利用队列这一数据结构来实现。因此主要包含两个方面,即队列这一数据结构中相关函数的设计与实现,以及如何实现深度优先搜索算法判断变量通分量的设计与实现。由于对队列已经比较熟悉,在这里仅作简要的说明。
(1)队列:
这里使用到的与队列相关的操作主要有栈中数据的初始化 QueueInitiate、将数据存入队列的操作 QueueAppend、将数据从队列中删除的操作 QueueDelete、判断队列是否为空的操作 QueueNotEmpty。
(2)查找与合并:在广度优先搜索中首先判断是否需要标记此节点,如果需要标记此节点则将此节点标记为以访问过,并添加到已经访问过的结点的集合中;如果是要进行判断两个结点是不是都已经访问过了,及是否属于同一个集合利用栈来不断的搜索其中一个结点所在的集合中是否有另一个结点,如果存在则舍弃当前所选择的边,否则选择此边为最小生成树的一边。
下面给出 kruakal 算法利用广度优先搜索进行边连通分量查询和合并从而得到最小生成树的的设计与实现步骤:
(1)对所画区域进行刷新。
(2)对已经排好序的边进行选择,对没有访问过的最小权值的边的两个结点进行判断,检查是否已经被访问过了,如果有一个没有被访问过,则将和此边相应的顶点进行广度优先搜索的判断之后进行标记,同时画出所选择的这个边和相应的顶点。
(3)如果都已经被访问过了,则利用广度优先搜索判断这两个节点是否属于同一个集合,如果是的话则抛弃此边,如果不是的话则对其进行标记,并画出此边和相对应的点。
(4)选择下一条没有被访问过的边重新进行(1)、(2)的判断,直到所有的顶点均已被访问过且在同一个集合中,即已经添加到了最小生成树中则最小生成树生成完毕。
(5)当最小生成树生成完毕时,则调用 Draw(E)函数画出生成的过程。
2.6 画图模块
这一模块主要是实现如何动态的演示程序运行的效果,主要涉及的有三个方面,第一个方面是使用不同的算法实现最小生成树的绘制过程,第二个方面是画图区域的刷新,第三个方面是并查集的绘制过程。
对于最小生成树的绘制过程有一个函数承担,主要是实现程序在调用 prime 算法、kruskal 算法、深度优先搜索实现的 kruskal 算法和广度优先搜索实现的 kruskal 算法的过程中
相关运行过程的绘制,此处主要通过判断最小生成树中所存储的边来进行绘制。
画图区域的刷新主要是为了实现同一块区域可以画多次不同的运行过程,有两个函数承担。由于并查集的绘制和最小生成树的绘制没有太大的关联,因此在这里采用了单独绘制并查集实现 kruskal 算法中并查集的合并过程。
三. 系统测试 3.1 测试数据
图(2)
上图是利用程序直接得到的原图形,此测试数据中有七个顶点,有十条边。通过这些可知其生成的最小生成树只能有七个顶点、六条边。通过观察可知这六条边应为(2,3)、(6,7)、(2,4)、(4,5)、(4,6)、(1,2)。
3.2Primme 的测试结果
图(3)
通过上面 prime 算法的解析结果和运行结果发现其运行结果与分析中应该得到的结果是一致的,由于画图和判断中采用的有延长运行时间的函数,因此这里只通过理论分析得出prime 算法的运行效率。
3.2Kruskal 算法的测试结果
图(4)
通过上面 kruskal 算法的解析结果和运行结果发现其运行结果与分析中应该得到的结果是一致的,由于画图和判断中采用的有延长运行时间的函数,因此这里只通过理论分析得出kruskal 算法的运行效率。
3.3 并查集实现 Kruskal 算法的测试结果
图(5)
此图中首先给出了最初集合的状况,紧接着给出了每一次进行边通分量查找合并过程中发生变化的集合的状况。通过此图并结合上面对并查集的分析可知与其运行一致。
3.4 深度优先搜索实现 Kruskal 算法的测试结果
图(6)
在这里没有对深度优先搜索的过程给予动态显示,主要是模拟了深度优先搜索实现kruskal 算法的过程,也即最小生成树的生成过程。通过对比前两种 kruskal 算法的实现过程可知其运行是一致的。
3.5 广度优先搜索实现 Kruskal 算法的测试结果
图(7)
通过与其他方法实现 kruska 算法进行对比,可知结果是一致的。由此也说明一个问题,即对于使用不同的方法来实现这一算法,改变的只是其效率,但是整体的运行情况是不会发生改变的。因此在实现的过程中应该尽量选择效率比较高的方法来实现算法。
对于广度优先搜索每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接 点的过程。因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同,两者不同之处仅在于对顶点访问的顺序不同。对于使用 kruskal 算法和深度优先搜索结合的算法,对边的遍历至多是 e 次,故其总代价为 O(n^2*e)。
3.6 效率分析 Prime 算法实现的函数主要是一个两重循环,其中每一重循环的次数均为顶点个数 n,所以该算法的时间复杂度为 O(n^2)。
Kruskal 算法的时间复杂度与选取的排序函数有关,这里采用的是不是对其进行排序 而是在每一次循环中找余下的边中权值最小的边,找到最小的边之后将对其相应的点进行标记,已知点的个数为 n 边的个数为 e,所以它的时间复杂度为最坏的情况下为 O(e^2),如果边已经很有序的话,也就是最好的情况下的时间复杂度为 O(n^2)。
Kruskal 运用并查集实现中使用了路径压缩,Find 和 UNION 函数几乎是常数假设可能对几乎所有边都判断过了,则最坏情况下算法时间代价为 O(eloge),即堆排序的时间通常情况下只找了接近顶点数目那么多边的情况下,MST 就已经生成,时间代价接近于 O(nloge)
深度优先搜索对每一条边处理一次,每个顶点访问一次以邻接矩阵作存储结构:处理所 有的边需 O(n n^2)的时间 ,故总代价为 O(n^2)。对于使用 kruskal 算法和深度优先搜索结合的算法,对边的遍历至多是 e 此故其总代价为 O(n^2*e)。
四. 总结 这个题目的主要要求是通过使用不同的算法求出图的最小生成树,并且通过画图动态的显示出来其不同的算法在求解最小生成树时的运行步骤。在我的程序中已经实现了对给出的这一例子使用 Prime 算法、Kruskal 算法求解最小生成树的运算过程的动态显示,除此之外,对于还实现了在边通分量的查询与合并的过程中,采用广度优先搜索算法(Breadth First Search)、深度优先搜索算法(Depth First Search)和并查集(Union-Find Set)三种方法来实现对此例中图的最小生成树的求解,主要是将这三种搜索方法与 Kruakal 结合来实现对最小生成树的求解。
虽然通过例子实现了使用题目中要求的算法来求解最小生成树,但是没能实现给用户一个友好的界面来方便求解各种不同的图的最小生成树,只能通过改变程序里面相关的存储变量来实现对不同图的最小生成树的求解。同时由于对于作图这方面不是很熟练,没能实现对图的动态扩充,所以只能是实现对一定数目,一定边数的图的求解。为了我的程序更加完美我会继续努力,从而实现图的动态扩充,同时让程序更为简练。
在最初选择题目的时候,总是觉得自己对使用 MFC 来画图这一方面不是很熟悉,担心自己做不出来。在实现在边通分量的查询与合并的过程中,采用广度优先搜索算法(Breadth
First Search)、深度优先搜索算法(Depth First Search)和并查集(Union-Find Set)三种方法来实现对此例中图的最小生成树的求解,这一方面最初也是相当的纠结,不知道该从什么方面下手。因为在学习数据结构的时只知道广度优先搜索算法(Breadth First Search)、深度优先搜索算法(Depth First Search)是用来遍历图的,平时没有在搜索的过程中使用此种算法,不知道该从何下手,通过老师的讲解多多少少悟出了点,之后反复的思考最终通过使用队列实现了在边通分量的查询与合并的过程中,采用广度优先搜索算法(Breadth First Search),通过使用栈实现了在边通分量的查询与合并的过程中,深度优先搜索算法(Depth First Search)。
这让我意识到学习到的知识一定要活用才能创造出更好的方法,只是使用它通常的用途是远远不够的。
虽然做的时候还是很多都不熟悉,但是我知道如果我不尝试这去做的话就真的什么也做不出来了。虽然最后做的和自己最初设想的有所差异,但是题目中的要求我都完成了,还是小有成就感的。所以通过这次的实习,让我认识到只要去尝试,去努力没有什么是不可以做的。
参考文献:
[1]朱战立,数据结构—使用 c 语言(第四版),电子工业出版社 2010 年 11 月 [2]王桂平、王衍、任嘉辰,图论算法理论、实现及应用,北京大学出版社,2011 年 1 月 [3]孙鑫、余安萍,VC++深入详解,电子工业出版社 2011 年 5 月
- 范文大全
- 职场知识
- 精美散文
- 名著
- 讲坛
- 诗歌
- 礼仪知识
-
2024年全国两会精神大学生心得感想
2024年全国两会精神大学生心得感想 在这个充满希望的春天,2024年全国两会如期而至,即使远在异国他乡,当我看到代表委员们用心用情履
【心得体会】 日期:2024-03-12
-
中国传统故事英文版 中国古代故事英文版
历史学科蕴含着许多丰富的、生动的、有趣的素材,每一个历史事件、历史人物都有相关的、动人的历史小故事,都能给人以启迪。你对中国古代的故事了解多少呢?下面是小编为您...
【调查报告】 日期:2019-05-22
-
2024年度纪律教育月活动方案6篇
2024年度纪律教育月活动方案6篇各级各部门要充分认识加强纪律教育、推进纪律建设的重要意义,高度重视、周密筹划、精心组织。在真抓实
【企划方案】 日期:2024-01-18
-
十八大以来我国网络安全和信息化辉煌成就
十八大以来我国网络安全和信息化的辉煌成就 党的十八大以来,以习近平同志为核心的党中央坚持从发展中国特
【申报材料】 日期:2020-11-25
-
雷锋日是什么时候几月几日_学雷锋日是几月几日
雷锋日是用来纪念雷锋同志的,也有很多人用这一天来学习雷锋助人为乐。雷锋日是什么时候呢?下面小编为大家推荐一些雷锋日的时间及相关知识,希望大家有用哦。 雷锋...
【入团申请书】 日期:2019-05-08
-
2篇,学习对于构建现代化经济体系新发展格局心得体会
2篇学习关于构建现代化经济体系新发展格局的心得体会篇一: “建设现代化经济体系&rdqu
【慰问贺电】 日期:2020-12-08
-
2022年全国节约用水知识大赛题库(含答案)
22022年全国节约用水知识大赛题库(含答案) 单选题(总共153题) 1 习近平总书记站在可持续发
【工作计划】 日期:2021-07-23
-
2023 年全省“安全生产月”活动方案
2023 年全省安全生产月活动方案 组织开展安全生产大家谈班前会以案说法等学习交流体会活动。以下是蒲公英阅读网小编为大家收集的内容,希
【企划方案】 日期:2023-05-30
-
【国庆节中学黑板报】 中学生防溺水黑板报
革命先烈的英雄事迹,我们不会忘却,他们永远活在我们的心里。下面就随小编看看国庆节中学黑板报内容,希望喜欢哦。 国庆节中学黑板报图片欣赏 国庆节中学黑板报...
【调查报告】 日期:2019-05-05
-
男的脸上毛孔粗有黑头怎么办_男士有黑头毛孔粗大
很多男生随着年龄的增长会发现脸上的皮肤越来越不如从前,有的甚至毛孔粗大还出现了黑头。那么,男的脸上毛孔粗有黑头怎么办呢?下面跟着小编一起来了解一下吧。 男生...
【学习体会】 日期:2019-05-13
-
执行信息公开网
执行信息公开网 执行信息公开网 执行信息公开网: zhi*ing (点击下图可直接进行访问) 全国
【职场知识】 日期:2020-07-03
-
乙酸乙酯皂化反应速率常数测定实验报告
学号:201114120222 基础物理化学实验报告 实验名称: 乙酸乙酯皂化反应速率常数的测定 应
【职场知识】 日期:2020-09-29
-
“从青风公司审计案例看销售与收款循环审计”案例说明书
“从青风公司审计案例看销售与收款循环审计”案例说明书一、本案例要解决的关键问
【职场知识】 日期:2020-09-28
-
机械加工创业项目_加工小本创业项目
现在在加工创业项目办小本加工厂有哪些?有什么项目推荐,下面这些小本加工厂项目个个都适合一个人创业,来看看吧!以下是小编分享给大家的关于,一起来看看加工小本创业项目吧!...
【职场知识】 日期:2020-03-19
-
医院护士践行社会主义核心价值观演讲稿两篇
医院护士践行社会主义核心价值观演讲稿两篇本文关键词:践行,演讲稿,两篇,护士,核心价值观医院护士践行
【职场知识】 日期:2021-05-03
-
致橡树(中英文)
3 【原诗】 【JohannaYueh修改版】 致橡树TotheOakTree 作者:舒婷ByShu
【职场知识】 日期:2020-11-17
-
《高等学校课程思政建设指导纲要》及全文内容解读
最新《高等学校课程思政建设指导纲要》及全文内容解读 一、 《纲要》 出台的背景和重要意义 二、 全面
【职场知识】 日期:2020-08-21
-
民主评议党员制度实施细则
民主评议党员制度实施细则 第一章总则 第一条为贯彻落实全面从严治党要求,进一步推进民主评议党员工作科学化、规范化、制度化,根据
【职场知识】 日期:2022-06-16
-
动量守恒定律专题训练含答案
动量守恒定律专题训练含答案 一、不定项选择题 11、下列运动过程中,在任意相等时间内,物体动量变化不
【职场知识】 日期:2021-01-06
-
中性时尚帅气短发女发型设计图片 最潮帅气中性短发发型
时尚中性帅气短发女发型图片精选,想走中性风的MM不妨进来看看,为自己选一款好看的新发型。下面是小编为大家整理的中性帅气短发女发型图片,供大家参考! 中性帅气短发女发...
【职场知识】 日期:2020-03-15
-
唐代诗人李昂个人信息
唐代诗人李昂个人信息 导读:我根据大家的需要整理了一份关于《唐代诗人李昂个人信息》的内容,具体内容:
【古典文学】 日期:2020-11-07
-
[关于中秋的朗诵诗词] 关于爱国的朗诵诗词
中秋,热闹的街头树起了灯彩,舞起了火龙。你知道多少关于中秋的朗诵诗词?下面小编为你整理了几篇关于中秋的朗诵诗词,希望对你有帮助。 关于中秋的朗诵诗词一 中秋佳节...
【古典文学】 日期:2019-06-06
-
法律知识手抄报图片大全|法律知识手抄报
我国开展了全面的普法宣传工作,法制宣传教育、普及法律常识作为经常的重要任务。做法制教育手抄报,普及法律知识。下面是小编为大家带来的法律知识手抄报图片大全,希望大家...
【古典文学】 日期:2020-03-10
-
食品中脂肪测定(索氏提取法)实验报告
报告汇编Compilationofreports20XX 报告文档·借鉴学习word可
【古典文学】 日期:2020-10-18
-
高血压论文参考文献
高血压论文的参考文献 [1] 中国高血压防治指南2010 ? 《中华心血管病杂志》 被中信所《中国科
【古典文学】 日期:2020-06-04
-
创业思路 [20个创业思路]
在家创业好项目,想创业,不想出门,有没有什么好方法呢?要想兼顾全职的工作,又想挣点外快,我们来看看这些项目。以下是小编为大家整理的关于20个创业思路,给大家作为参考,...
【古典文学】 日期:2020-03-02
-
读《数学教育的"中国道路"》有感 数学教育的中国道路
读《数学教育的中国道路》有感 中山市博爱初级中学李丽敏 一开始拜读张奠宙教授的《数学教育的中国道路》一书,想着,这么大的问题,是我这个小小的一线
【古典文学】 日期:2019-05-05
-
历史爱国人物故事_爱国人物故事简短
每一个历史事件、历史人物都是一个动人的小故事,都能给人以启迪。无论是现在还是以往都有爱国人物的故事,下面是小编为您整理的历史爱国人物故事,希望对你有所帮助! 历史...
【古典文学】 日期:2019-05-06
-
2017烧显卡的游戏排行榜 2017年最烧显卡的游戏
作为一名游戏党,当然关注的是显卡,显卡是游戏的第一条件,那么烧显卡的游戏有哪些呢?下面是有2017烧显卡的游戏排行榜,欢迎参阅。 2017烧显卡的游戏排行榜 1、《孤岛...
【古典文学】 日期:2020-02-23
-
各类岗位薪级工资正常晋升对照表
各类岗位工资及薪级工资对照表:专业技术职务岗位工资及薪级工资对照表 岗位工资薪级工资岗位工资标准薪级
【古典文学】 日期:2020-09-23
-
雪天安全行车注意事项_雪天安全行车提示语
维护城市交通秩序,争做河源文明市民。你们想看看雪天安全行车提示语有哪些吗?以下是小编推荐雪天安全行车提示语给大家,欢迎大家阅读! 安全行车温馨提示语【经典篇】 1...
【中国文学】 日期:2020-03-15
-
【世界上最大的半岛】阿拉伯半岛
你知道世界上最大的半岛是什么吗?下面由小编来介绍一下。 阿拉伯半岛的简介 阿拉伯半岛(阿拉伯文:)位于亚洲,是世界上最大的半岛。沙特阿拉伯、也门、阿曼、阿拉伯联合...
【中国文学】 日期:2019-05-24
-
小数乘法计算方法
小数乘法得计算方法理解小数乘法计算得法则,能够比较熟练得进行小数乘法笔算与简单得口算重点掌握小数乘法
【中国文学】 日期:2020-12-22
-
世界上国家间最大的陆地争议地区是什么:世界上有几个国家地区
古往今来,国土分界线就是兵家常争之地,大家又知不知道世界上国家间最大的陆地争议地区呢?现在就由小编为大家介绍这块世界上国家间的最大陆地争议地区吧! 世界上国家间的...
【中国文学】 日期:2020-02-28
-
特种设备作业人员作业种类与项目目录
特种设备作业人员作业种类与项目目录 种类 作业项目 项目代号 备注 特种设备相关管理特种设备安全管理
【中国文学】 日期:2020-09-23
-
【欧式女装小店面装修图】 女装小店面装修
随着服装行业和照明产业的发展日趋成熟,服装店的照明设计越来越受到人们的广泛关注,即通过光环境设计对消费者产生引导性作用。下面小编就为大家解开欧式女装小店面装修图展...
【中国文学】 日期:2020-02-27
-
清明节踏青简笔画【清明节踏青图片】
清明节是二十四节气之一,是很适合出去踏青的节日,下面是小编为大家收集的清明节踏青图片相关资料,希望对大家有所帮助。 清明节踏青图片欣赏 清明节踏青图片1 清明...
【中国文学】 日期:2019-05-08
-
电磁场与电磁波实验报告
实验一 静电场仿真 1 实验目的建立静电场中电场及电位空间分布的直观概念。 2 实验仪器计算机一台3
【中国文学】 日期:2020-08-26
-
廉政风险点及防控措施
廉政风险点及防控措施 廉政风险点廉政风险点及防控措施 一、思想道德及制度机制 (一)思想道德(二级风
【中国文学】 日期:2020-07-02
-
史玉柱创业故事_创业故事白手起家故事
史玉柱,一个有着传奇和神话般经历的人,而且,这个传奇和神话正在续写。下面小编就为大家解开史玉柱创业故事,希望能帮到你。 史玉柱创业故事篇一 史玉柱的创业史可以分为...
【中国文学】 日期:2020-02-28
-
国家开放大学电大公文文体写作试题及答案
公文文体的写作(二)单元测试题 1 决定属于A.上行文B.下行文C.平行文D.既可上行也可下行 2
【外国名著】 日期:2020-07-02
-
山东省生产经营单位安全生产主体责任规定(303号令)
山东省生产经营单位安全生产主体责任规定(2013年2月2日山东省人民政府令第260号公布根据2016
【外国名著】 日期:2020-10-22
-
传感器测试实验报告
实验一 直流激励时霍尔传感器位移特性实验一、实验目得:了解霍尔式传感器原理与应用。 二、基本原理:金
【外国名著】 日期:2020-11-09
-
六年级下册《比例尺》单元测试题
一、填空题: 1、比例尺=( ):( ),比例尺实际上是一个( )。 2、一幅图的比例尺是。A、B两
【外国名著】 日期:2020-09-29
-
人教版高一语文必背 人教版高一语文《老王》赏析
杨绛的《老王》,可谓是平凡的人平常的事,平淡的语言平常的心,但读来总让人印象深刻,感触颇多,下面是小编给大家带来的人教版高一语文《老王》赏析,希望对你有帮助。 高一...
【外国名著】 日期:2020-03-10
-
“坚定理想信念、增强历史自觉、弘扬优良传统、加强党性锤炼、党员先锋模范作用发挥”方面存问题和不足剖析材料例文
“坚定理想信念、增强历史自觉、弘扬优良传统、加强党性锤炼、党员先锋模范作用发挥&rdqu
【外国名著】 日期:2021-08-14
-
【缅怀革命先烈黑板报图片】缅怀革命烈士黑板报
中国的抗日名将是数不胜数,其中张灵甫大家了解多少呢?下面就随小编看看缅怀革命先烈的黑板报内容,希望喜欢哦。 缅怀革命先烈黑板报图片欣赏 缅怀革命先烈黑板报图片1...
【外国名著】 日期:2019-05-09
-
3.8妇女节_3.8妇女节手工制作图片精选
3 8妇女节送卡片表示感恩与祝福是在好不过了,小编整理了3 8妇女节手工制作感恩卡图片,希望大家喜欢! 3 8妇女节手工制作感恩卡图片展示 3 8妇女节手工制作感恩卡图...
【外国名著】 日期:2020-03-14
-
《中小学教师违反职业道德行为处理办法》实施细则
《中小学教师违反职业道德行为处理办法》实施细则本文关键词:实施细则,职业道德,中小学教师,违反,办法
【外国名著】 日期:2021-03-24
-
金融术语中英文对照
ABS资产担保证券(AssetBackedSecurities的英文缩写) Acceleratedd
【外国名著】 日期:2020-07-03
-
梧桐花的花语|梧桐花的功效与作用
梧桐花为梧桐科植物梧桐的花,植物形态详梧桐子条。今天小编为你整理了梧桐花的花语,欢迎阅读。 梧桐花的花语是:情窦初开 在春季里晚开的花朵,有着恬淡的气息。 ...
【寓言童话】 日期:2020-03-03
-
惊悚鬼故事50字 令人惊悚的故事
这些惊悚故事在短短的篇幅和时间之内让您感受到故事里传达出来的恐怖感,令你感到害怕。下面就是小编给大家整理的令人惊悚的故事,希望对你有用! 令人惊悚的故事篇1:学校...
【寓言童话】 日期:2019-05-13
-
大学生音乐欣赏论文 大学音乐鉴赏论文3000
今天小编就为你介绍关于大学生音乐欣赏论文,下面是!小编给你搜集了相关资料!希望可以能帮助到大家。 大学生音乐欣赏论文—第一篇 音乐是生活不可缺少的一部分,学会欣...
【寓言童话】 日期:2020-03-12
-
西部计划笔试题库(99题含答案)
西部计划笔试题库(99题含答案) 1 第十三届全国人大三次会议表决通过了《中华人民共和国民法典》,自
【寓言童话】 日期:2021-06-16
-
廉洁自律自我剖析材料(精选)
廉洁自律自我剖析材料((精选多篇)) 信念。科学文化,提高自身素质的终身学习的意识,紧密联系群众,调
【寓言童话】 日期:2020-07-20
-
【名人失败的故事】 关于失败的名人故事
我们最大的弱点在于放弃。成功的必然之路就是不断的重来一次。涓滴之水终可以磨损大石,不是由于它力量强大,而是由于昼夜不舍的滴坠。下面是小编为您整理的名人失败的故事,...
【寓言童话】 日期:2019-05-19
-
康熙字典五行属金的字 [字典中八画五行属金的字信息大全]
在五行中不同属性的字寓意是不相同的,其实同样的属性不同的笔画的字寓意也是一样的,下面小编为你整理了八画五行属金字,希望对你有所帮助! 8画五行属金的字 忮、8画、...
【寓言童话】 日期:2020-03-12
-
【儿童动物的故事大全】 儿童动物故事100篇
对于听故事,几乎所有的儿童都有一个共同点就是百听不厌。一个故事重复数十遍,儿童听时同样要注意力集中,眼睛凝视着讲述者的动作,眼神聚精会神,表现出极大的兴趣。、下面是小编...
【寓言童话】 日期:2019-05-31
-
[人工智能对人类影响英文作文] 人工智能对人类的影响
人工智能就是人造智能,其英文表示是“ArtificialIntelligence”,简称AI。以下是小编整理的人工智能对人类影响英文作文的相关资料,欢迎阅读! 人工智能对人类影响英文作文...
【寓言童话】 日期:2019-05-05
-
[文言文虚词于的用法]虚词于的意义和用法
“文言文”的意思就是指“美好的语言文章”也叫做语体文。文言文虚词于的用法有哪些呢?下面是小编整理的关于文言文虚词于的用法,欢迎阅读 文言文虚词于作为名词的用法 ...
【寓言童话】 日期:2020-03-20
-
学生高考动员演讲稿
学生高考动员演讲稿3篇高考动员演讲稿11 老师们、同学们: 大家下午好!漫漫高考长征路已经进入尾声了
【百家讲坛】 日期:2021-09-22
-
企业安全演讲稿2021
最新企业安全的演讲稿5篇 演讲稿是作为在特定的情境中供口语表达使用的文稿。在充满活力,日益开放的今天
【百家讲坛】 日期:2021-09-22
-
XX镇扶贫项目实施专项整治工作总结_1
XX镇扶贫项目实施专项整治工作总结 为深入贯彻精准扶贫精准脱贫基本方略,认真落实党中央、国务院,省委
【百家讲坛】 日期:2021-09-22
-
对乡镇领导班子干部成员批评意见例文
对乡镇领导班子干部成员的批评看法范文 一、对党委书记XXX同志的批评看法〔3条〕 1、与干部交流偏少
【百家讲坛】 日期:2021-09-22
-
群英乡扶贫资金项目芬坡村祖埇村生产道路硬化工程绩效自评报告
群英乡扶贫资金项目((芬坡村祖埇村生产道路硬化工程))绩效自评报告 一、基本情况(一)群英乡扶贫资金
【百家讲坛】 日期:2021-09-22
-
党委书记警示教育大会上讲话2021汇编
党委书记在警示教育大会上的讲话55篇汇编 党委书记在警示教育大会上的讲话(一) 同志们: 根据省州委
【百家讲坛】 日期:2021-09-22
-
对于2021年召开巡视整改专题民主生活会对照检查材料
关于12021年召开巡视整改专题民主生活会对照检查材料 按照中央巡视组要求和省、市、区委统一部署,区
【百家讲坛】 日期:2021-08-14
-
消防安全知识培训试题.doc
消防安全知识培训试题姓名: 部门班组: 成绩: 一:填空题,每空4分,共44分。 1、灭火剂是通过隔
【百家讲坛】 日期:2021-08-14
-
涉疫重点人员“五包一”居家隔离医学观察工作流程
涉疫重点人员“五包一”居家隔离医学观察工作流程 目前,全球疫情仍处于大流行状
【百家讲坛】 日期:2021-08-14
-
疫情防控致全体师生员工及家长一封信
疫情防控致全体师生员工及家长的一封信 各位师生员工及全体家长朋友: 暑假已至,近期我省部分地方发现确
【百家讲坛】 日期:2021-08-14