- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
大数据技术与应用专业教学资源库
《数据结构》课程说课稿
《数据结构》期末考试试卷A卷-简答题6
主讲:章万静
序号
PPT
说课稿
幻灯片 1
大家好。我是《数据结构》课程的主讲教师——章老师。
下面我们开始重点分析试卷A中的题目。
幻灯片 2
我们来看一下简答题。
幻灯片 3
简答题的第6题。
画出下图的最小生成树。
这道题5分。
我们知道,最小生成树要掌握下面三个要点:
1、6个顶点的最小生成树应该有5条边,5条边的权值加起来和最小,而且5条边能让6个顶点是连通的,并且没有闭合的回路。
2、最小生成树有2种方法:普里姆算法,克鲁斯卡尔算法。
3、最小生成树有可能不是唯一的。
幻灯片 4
第一种方法,普里姆算法生成最小生成树。这种方法是从顶点出发,每增加一个顶点,就会新增一条边,直到增加到6个顶点5条边为止,注意不能产生回路。
我们来分析普里姆算法生成最小生成树的详细过程:
第一步:以A为源点,看看其他那个顶点到A的连线权值最小。C到A的权值为3,最小。那么就新增一个顶点C,新增一条边3。
第二步:以A或C为出发点,看看其他那个顶点到A或C的连线权值最小。 B到C的权值为3,最小。那么就又新增一个顶点B,又新增一条边3。
第三步:以A、B或C为出发点,看看其他那个顶点到A、B或C的连线权值最小。E到A的权值为4,最小。那么就又新增一个顶点E,又新增一条边4。
第四步:以A、B、C或E为出发点,看看其他那个顶点到A、B、C或E的连线权值最小。F到E的权值为4,最小。那么就又新增一个顶点F,又新增一条边4。
第五步:以A、B、C、E或F为出发点,看看其他那个顶点到A、B、C、E或F的连线权值最小。F到A的权值为5,最小,但是这条边不能用,它会让AEF构成回路,必须舍弃。B到A的权值也为5,最小,但是这条边也不能用,它会让ABC构成回路,也必须舍弃。剩下就是D到A,或者D到C的权值为8,最小。这2条边随便选择一条都可以,选择的边不一样,最小生成树的结构也不一样,所以说最小生成树可能不是唯一的。这里,我们随便选择一条边,就选D到C这条边,那么就又新增一个顶点D,又新增一条边8。
通过上面这样五步,普里姆算法就实现了最小生成树,6个顶点5条边,没有回路。
幻灯片 5
第二种方法,克鲁斯卡尔算法生成最小生成树。这种方法是从边出发,每确定一条边,新增一些顶点,直到确定5条边6个顶点为止,注意不能产生回路。
我们来分析克鲁斯卡尔算法生成最小生成树的详细过程:
第一步:在所有的边中,看看那条边的权值最小。A到C,或者B到C的权值为3,最小,我们任意选择一条边,B到C。那么就确定了一条边3,2个顶点B、C。
第二步:在剩下的边中,看看那条边的权值最小。A到C的权值为3,最小。那么就新增一条边3,新增一个顶点A。
第三步:在剩下的边中,看看那条边的权值最小。E到A,或者E到F的权值为4,最小,我们任意选择一条边,E到F。那么就又新增一条边4,新增两个顶点E、F。
第四步:在剩下的边中,看看那条边的权值最小。E到A的权值为4,最小。那么就又新增一条边4,没有新增顶点。
第五步:在剩下的边中,看看那条边的权值最小。 F到A的权值为5,最小,但是这条边不能用,它会让AEF构成回路,必须舍弃。B到A的权值也为5,最小,但是这条边也不能用,它会让ABC构成回路,也必须舍弃。剩下就是D到A,或者D到C的权值为8,最小。这2条边随便选择一条都可以,选择的边不一样,最小生成树的结构也不一样,所以说最小生成树可能不是唯一的。这里,我们随便选择一条边,就选D到A这条边,那么就又新增一条边8,新增一个顶点D。
通过上面这样五步,克鲁斯卡尔算法就实现了最小生成树,5条边6个顶点,没有回路。
幻灯片 6
本次微课就介绍到这里,希望大家好好理解与掌握。谢谢观看。
您可能关注的文档
- 数据结构-3期(KC002)实训项目库万达停车场管理系统设计.docx
- 数据结构与算法设计教案05-06-2数据结构教案首页(40541P、40543D、40531P).doc
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题1-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题3-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题4-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题5-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题7-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题8-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷B卷-简答题1-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷B卷-简答题2-配套说课稿.docx
文档评论(0)