当前位置: 首页 > news >正文

建筑模板是干什么用的南昌seo计费管理

建筑模板是干什么用的,南昌seo计费管理,wordpress插件途径,qq网页版手机版文章目录 最小生成树总览生成树广度优先生成树深度优先生成树最小生成树Prim算法Kruskal算法Prim vs KrusakalPrim的实现Kruskal的实现 小结 最短路径问题单源最短路径问题BFS求无权图的单源最短路径小结Dijkastra算法算法时间复杂度不适用情况 每一对顶点的最短路径问题Floyd算…

文章目录

  • 最小生成树
    • 总览
    • 生成树
    • 广度优先生成树
    • 深度优先生成树
    • 最小生成树
    • Prim算法
    • Kruskal算法
    • Prim vs Krusakal
      • Prim的实现
      • Kruskal的实现
    • 小结
  • 最短路径问题
    • 单源最短路径问题
      • BFS求无权图的单源最短路径
      • 小结
      • Dijkastra算法
        • 算法时间复杂度
        • 不适用情况
    • 每一对顶点的最短路径问题
      • Floyd算法
        • 找两个点的最短路径
        • 核心代码
        • 实例
        • 找两个顶点最短路径
        • Floyd用于负权图
        • 不能解决的问题
      • 小结

最小生成树

总览

在这里插入图片描述

生成树

在这里插入图片描述

广度优先生成树

在这里插入图片描述

深度优先生成树

在这里插入图片描述

最小生成树

针对的是带权连通图
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

Prim算法

同一个图的最小生成树可能不唯一

从p城出发
在这里插入图片描述
在这里插入图片描述

从农场出发也一样
在这里插入图片描述

Kruskal算法

在这里插入图片描述

Prim vs Krusakal

在这里插入图片描述

Prim的实现

先找到最低代价的节点,每次将节点加入树后,需要更新各节点加入树的最低代价(即将原来的代价和个节点与加入节点的代价作比较)
在这里插入图片描述

Kruskal的实现

查找并查集(如果用二叉树实现的)的根需要log2E
在这里插入图片描述

小结

在这里插入图片描述

最短路径问题

在这里插入图片描述

单源最短路径问题

BFS求无权图的单源最短路径

首先访问2号顶点,然后再更新其相邻顶点后的结果
在这里插入图片描述
然后1号顶点出队,相邻节点入队,同时更新各相邻节点
在这里插入图片描述
然后6号顶点出队,更新相邻节点,同时各个相邻节点入队
在这里插入图片描述
5号顶点没有相邻
所以到3号顶点处理
在这里插入图片描述
7号顶点处理
在这里插入图片描述
4号和8号相邻节点都被访问,所以没有处理

小结

在这里插入图片描述

Dijkastra算法

BFS局限性(默认每条路径长度一样)
在这里插入图片描述
初始化后,即更新初始节点及其相邻节点
在这里插入图片描述
第一轮后
在这里插入图片描述
第二轮后
在这里插入图片描述

第三轮后
在这里插入图片描述
第四轮后

在这里插入图片描述
查找两个顶点的最短路径
在这里插入图片描述

算法时间复杂度

在这里插入图片描述

在这里插入图片描述

不适用情况

在这里插入图片描述

每一对顶点的最短路径问题

在这里插入图片描述

Floyd算法

初始时
在这里插入图片描述
允许在v0中转
在这里插入图片描述
允许在v0 v1中转
在这里插入图片描述
允许在v0 v1 v2中转
在这里插入图片描述

找两个点的最短路径

在这里插入图片描述

核心代码

空间复杂度是有n*n个矩阵那么多
在这里插入图片描述

实例

初始
在这里插入图片描述
允许在v0中转
发现没有变化
从图可以发现v0没有进去的边,所以自然没法中转
在这里插入图片描述
允许在v0 v1中转
在这里插入图片描述
允许在v0 v1 v2中转
是已经基于之前v0 v1的中转结果的
例如v2到v3是基于中转v1的,但是在以v2中转的转换中是把它认为是相连的
在这里插入图片描述
在这里插入图片描述
允许在v0 v1 v2 v3中转

在这里插入图片描述
允许在v0 v1 v2 v3 v4中转
在这里插入图片描述

找两个顶点最短路径

在这里插入图片描述

Floyd用于负权图

在这里插入图片描述

不能解决的问题

回路越多,路径越短

在这里插入图片描述

小结

BFS 采用邻接矩阵是V的平方 邻接矩阵是V+E
在这里插入图片描述

http://www.mmbaike.com/news/33685.html

相关文章:

  • 常州百度关键词优化网站seo入门基础教程书籍
  • 四站合一网站制作优化排名
  • 俄罗斯网站建设公司百度普通下载
  • 最近新闻内容青海网站seo
  • 怎么做婚恋网站优化设计五年级下册数学答案
  • 引用网站的内容如何做注释网站统计平台
  • 电影网站建设步骤湖南做网站的公司
  • 网站开发实训设计报告湖南seo快速排名
  • 网站建设 报价seo关键词优化排名软件
  • 哪个公司做网站好 知乎扬州seo优化
  • wordpress文章发布添加项目北京网站sem、seo
  • 90后做网站月入万元西安互联网推广公司
  • 谷城网站快速排名seo交流网
  • ie兼容性 网站网站首页推广
  • 牡丹菏泽网站建设阿拉善盟seo
  • 工商企业注册登记网官网北京seo工程师
  • 江门免费建站seo招聘信息
  • 人社部门网站建设中国站长工具
  • 做网站在哪个地方买空间2024年4月新冠疫情结束了吗
  • 中文设计网站济南竞价托管公司
  • php网站开发示例代码自己如何注册网站
  • 备份文件wordpress贺州seo
  • 哈尔滨网站优化如何下载百度官方网站
  • 免费制作动画网站电话百度
  • 手机网站建google网站入口
  • 国外h5制作网站模板链接生成器在线制作
  • 怎么做网站排名优化免费seo推广培训学费
  • 怎么做网站的分类目录bt磁力
  • 新媒体网站建设十大的经典成功案例网络销售怎么才能找到客户
  • 建设网站的相关技术google chrome谷歌浏览器