学硕 专硕 非统考 考试大纲 历年真题 经验分享

热门直播 推荐课程 考研常识 网校名师 免费试听 考研首页

首页 > 考研专业课 > 计算机 >

2019计算机考研知识点:图的应用之最小生成树

2018-01-10 10:54 来源:文都网校 阅读()

  2019考研备考已经开始了,为帮助大家快速进入备考状态,文都网校考研频道小编特意帮大家整理了计算机考研的知识点:图的应用之最小生成树,希望对计算机考研的考生们有所帮助!

  图是数据结构科目中难度最大的重点章节,在这两年的考试中也作为重点来考查。图这部分内容概念多、算法多、难度大。这就需要大家深刻理解每个知识点,多做练习,抓住规律,才能很好地解答这部分试题。图这部分要求大家掌握图的定义、特点、存储结构、遍历、图的基本应用等内容。图这部分的重点和难点是图的基本应用,这在09年和10年的考试中有所体现。图的基本应用包括:最小生成树、最短路径、拓扑排序、关键路径等。09年考试中重点考查了最短路径的判断与证明。建议大家把图的基本应用作为重点来复习。

  下面介绍一下图的基本应用:

  一、最小生成树

  1.最小生成树的基本概念

  最小生成树:边的权值总和最小的生成树。最小生成树有很多重要的应用。

  2.最小生成树的性质 最小生成树性质:设G=(V,E)是一个连通网络,U是顶点集V的一个真子集。若(u,v)是G中一条“一个端点在U中(例如:u∈U),另一个端点不在U中的边(例如:v∈V-U),且(u,v)具有最小权值,则一定存在G的一棵最小生成树包括此边(u,v)。

  3.构造最小生成树的算法

  目前已有不少构造最小生成树的算法,建议大家重点复习两种常用的构造最小生成树的算法:普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。

  文都网校考研频道为大家持续更新考研资料,希望能帮助到大家,同学们可以关注文都考研,这里有你需要的资料,点击【kaoyan.wenduedu.com】风里、雨里,文都陪伴着你!有问题找文都☞☞☞详情咨询入口>>>

资讯推荐:

  全国各大高校2018考研成绩查询时间及入口

  历年考研复试分数线(34所自划线院校)

  2018考研复试备考指导汇总

  全国各院校2018考研调剂信息汇总

课程推荐:

1月主推课程

2018考研复试全程实战演练班

2018考研名校定向复试特训班

2019考研高端辅导成功卡

2019考研高端辅导英才成功卡

2019考研vip特训系列

2019考研VIP特训班【政英数】

2019考研专硕199管综VIP特训班

2019考研VIP特训班【政治 英语一】

2019考研VIP特训班【政治 英语二】

2019考研专硕VIP特训班【西医临综】

2019考研专硕会计硕士全科VIP特训班

 

责任编辑:lq

上一篇:2019计算机考研知识点:FTP 命令

下一篇:2019计算机考研知识点:图的应用之最短路径

关注官方微信
0元领取学习资料