• 尚大品牌
    • 尚大网校|在线考试|证书查询|成绩查询
    登录   |   注册
     
     
        准考证打印   论文投票   报考指南   论文辅导   软考培训   郑重申明  
    您现在的位置：  首页 > 软考学苑 > 信息系统项目管理师 > 高项上午综合知识 > 高项考点梳理 >> 正文
    正文
    8.1图论应用
    来源： 作者： 时间;2017-12-08 15:50:27 点击数： 尚大软考交流群：376154208
    8.1图论应用主要考查最小生成树、最短路径、关键路径等方面的问题。1）最小生成树一个连通且无回路的无向图称为树。在树中度数为1的节点成为树叶，度数大于1的节点成为分枝点或内结点。求连通的带权无向图的最小生成树的算法有普利姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。普利姆算法的特点是当前形成的集合T始终是一棵树。因为每次添加的边是使树中的
    <尚大教育，教育至上，人才为大：sdedu.cc>

     8.1图论应用

    主要考查最小生成树、最短路径、关键路径等方面的问题。

    1）最小生成树

    一个连通且无回路的无向图称为树。在树中度数为1的节点成为树叶，度数大于1的节点成为分枝点或内结点。

    求连通的带权无向图的最小生成树的算法有普利姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。

    普利姆算法的特点是当前形成的集合T始终是一棵树。因为每次添加的边是使树中的权尽可能小，因此这是一种贪心的策略。普利姆算法的时间复杂度为O(n2)，与图中边数无关，所以适合与稠密图。

    克鲁斯卡尔算法的特点是当前形成的集合T除最后的结果外，始终是一个森林。克鲁斯卡尔算法的时间复杂度为O(elog2e)，与图中顶点数无关，所以较适合于稀疏图。

    2）最短路径

    带权图的最短路径问题即求两个顶点间长度最短的路径，其中路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。

    迪杰斯特拉（Dijkstra）算法

    3）关键路径

    完成工程的最少时间是从开始节点到结束结点的最长路径长度，称从开始结点到结束结点的最长路径为关键路径（临界路径），关键路径上的活动为关键活动。

    <尚大教育，教育至上，人才为大：sdedu.cc>
     
       各省软考办 
     
    来顶一下
    返回首页
    返回首页
    上一篇： 第8章应用数学与经济管理
    下一篇： 8.2决策论
     相关文章
     
     
    跟贴共条
    查看完整评论
    笔 名 ：   验证码：
    网友评论仅供其表达个人看法，并不表明尚大教育同意其观点或证实其描述
    距离2023年05月27-28日软考考试还有 天
    尚大软考交流群：376154208
    软考各地考务机构
    更多>>
    全国 北京 天津 河北 山西
    内蒙古 辽宁 吉林 黑龙江 上海
    江苏 浙江 安徽 福建 江西
    山东 河南 湖北 湖南 广东
    广西 海南 重庆 四川 贵州
    云南 西藏 陕西 甘肃 青海
    宁夏 新疆 香港 澳门 宁波
    大连 兵团 报名入口 联系方式
    历年真题汇总
    更多>>




    各省市软考报名简章
    软考动态
    更多>>
    PMI, PMP, Project Management Professional, PgMP, PfMP, PMI-ACP, PMI-PBA, PMBOK and the PMI Registered Education Provider logo are registered marks of the Project Management Institute, Inc.   京ICP备12019404号  Copyright© 2008-2021 北京翰林尚大教育科技有限公司