2018计算机考研：图的基本应用之最小生成树
时间：2017-08-08 来源：文都网校 浏览：计算机考研的同学们，文都网校考研频道为大家提供计算机考研知识点，2018考研，你决定好了吗?来和小编一起看一下吧!希望对你们有所帮助!知识是不断的积累起来的，所以大家要赶快行动起来!
图是数据结构科目中难度最大的重点章节，在这两年的考试中也作为重点来考查。图这部分内容概念多、算法多、难度大。这就需要大家深刻理解每个知识点，多做练习，抓住规律，才能很好地解答这部分试题。图这部分要求大家掌握图的定义、特点、存储结构、遍历、图的基本应用等内容。图这部分的重点和难点是图的基本应用，这在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考研，文都一路相随!
资讯推荐：
课程推荐：
|
2018/2019考研 |
|
|
特训班系列 |
成功卡系列 |
|
文都直播 |
|
- 2018考研 计算机考研 图的基本应用之
- 责任编辑：lq
