位置: 编程技术 - 正文

JavaScript数据结构和算法之图和图算法(javascript数据结构与算法第三版)

编辑:rootadmin

推荐整理分享JavaScript数据结构和算法之图和图算法(javascript数据结构与算法第三版),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:js树结构数据,javascript数据结构与算法第三版pdf下载,javascript数据结构与算法,javascript数据结构与算法 pdf,javascript数据结构与算法第三版,javascript数据结构,javascript数据结构,javascript数据结构,内容如对您有帮助,希望把文章链接给更多的朋友!

图的定义

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

有向图

有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也成为弧(Arc),用有序偶<Vi,Vj>来表示,Vi称为弧尾,Vj称为弧头。

无序图

无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示。

简单图

简单图:在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。

图类

表示顶点

创建图类的第一步就是要创建一个Vertex类来保存顶点和边。这个类的作用和链表、二叉搜索树的Node类一样。Vertex类有两个数据成员:一个用于标识顶点,另一个表明是否被访问过的布尔值。分别被命名为label和wasVisited。

我们将所有顶点保存在数组中,在图类里,可以通过他们在数组中的位置引用他们

表示边

图的实际信息都保存在“边”上面,因为他们描述了图的结构。二叉树的一个父节点只能有两个子节点,而图的结构却要灵活得多,一个顶点既可以有一条边,也可以有多条边和它相连。

我们将表示图的边的方法成为邻接表或者邻接表数组。它将存储由顶点的相邻顶点列表构成的数组

构建图

定义如下一个Graph类:这个类会记录一个图表示了多少条边,并使用一个长度与图的顶点数来记录顶点的数量。

这里我们使用for循环为数组中的每个元素添加一个子数组来存储所有的相邻顶点,并将所有元素初始化为空字符串。

图的遍历

深度优先遍历

JavaScript数据结构和算法之图和图算法(javascript数据结构与算法第三版)

深度优先遍历(DepthFirstSearch),也有称为深度优先搜索,简称为DFS。

比如在一个房间内寻找一把钥匙,无论从哪一间房间开始都可以,将房间内的墙角、床头柜、床上、床下、衣柜、电视柜等挨个寻找,做到不放过任何一个死角,当所有的抽屉、储藏柜中全部都找遍后,接着再寻找下一个房间。

深度优先搜索:

深度优先搜索就是访问一个没有访问过的顶点,将他标记为已访问,再递归地去访问在初始顶点的邻接表中其他没有访问过的顶点

为Graph类添加一个数组:

深度优先搜索函数:

广度优先搜索

广度优先搜索(BFS)属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。

广度优先搜索从第一个顶点开始,尝试访问尽可能靠近它的顶点,如下图所示:

其工作原理为:

1. 首先查找与当前顶点相邻的未访问的顶点,将其添加到已访问顶点列表及队列中; 2. 然后从图中取出下一个顶点v,添加到已访问的顶点列表 3. 最后将所有与v相邻的未访问顶点添加到队列中下面是广度优先搜索函数的定义:

最短路径

在执行广度优先搜索时,会自动查找从一个顶点到另一个相连顶点的最短路径

确定路径

要查找最短路径,需要修改广度优先搜索算法来记录从一个顶点到另一个顶点的路径,我们需要一个数组来保存从一个顶点操下一个顶点的所有边,我们将这个数组命名为edgeTo

拓扑排序算法

拓扑排序会对有向图的所有顶点进行排序,使有向边从前面的顶点指向后面的顶点。拓扑排序算法与BFS类似,不同的是,拓扑排序算法不会立即输出已访问的顶点,而是访问当前顶点邻接表中的所有相邻顶点,直到这个列表穷尽时,才会将当前顶点压入栈中。

拓扑排序算法被拆分为两个函数,第一个函数是topSort(),用来设置排序进程并调用一个辅助函数topSortHelper(),然后显示排序好的顶点列表

拓扑排序算法主要工作是在递归函数topSortHelper()中完成的,这个函数会将当前顶点标记为已访问,然后递归访问当前顶点邻接表中的每个顶点,标记这些顶点为已访问。最后,将当前顶点压入栈中。

Javascript核心读书有感之类型、值和变量 计算机程序的运行需要对值(value)比如数字3.或者文本"helloworld"进行操作,在编程语言中,能够表示并操作的值的类型叫做数据类型(type),编程语言最基

JavaScript数据结构和算法之二叉树详解 二叉树的概念二叉树(BinaryTree)是n(n=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点

Javascript核心读书有感之表达式和运算符 表达式是javascript中的一个短语,javascript解释器会将其计算出一个结果。程序中常用量是最简单的一类表达式就是变量。变量名也是一种简单的表达式,

标签: javascript数据结构与算法第三版

本文链接地址:https://www.jiuchutong.com/biancheng/383903.html 转载请保留说明!

上一篇:javascript中var的重要性分析(javascript中var的作用)

下一篇:Javascript入门学习第四篇 js对象和数组第1/2页(javascript零基础入门)

  • 当期所得税是否是当期缴纳的所得税
  • 计提环境保护税怎么计算
  • 摊销无形资产商标权计入什么科目
  • 向保险公司缴纳的保险费可以税前扣除吗
  • 住宿税率是多少 5%
  • 需要冲红的普通发票无法收回怎么办
  • 物流辅助服务属于什么费用
  • 收到投资款怎么做会计凭证
  • 未取得房屋产权证的房屋法院可以拍卖吗
  • 在建工程领用原材料的账务处理
  • 库存商品的成本核算
  • 复利现值和复利终值的计算
  • 商场积分兑换现金怎么用
  • 房屋租赁合同样本书
  • 帮别的公司做账的叫什么公司
  • 开专用发票的地址有错会有影响吗?
  • 装修行业一般纳税人税负率是多少
  • 代缴水电费是什么意思
  • 代理记账公司收费标准
  • 制造费用在利润表体现吗
  • 公司购买的办公桌椅属于固定资产吗
  • 汽车厂家金融贴息 是贴利息的还是贴车价
  • 按年缴纳年金的企业缴费部分,应按照全年一次性奖金
  • 包工不包料都包括什么
  • 笔记本电脑的触摸板怎么用右键
  • win7系统中如何让未响应的程序继续运行
  • linux操作系统有哪些版本
  • 国家占耕地补偿款给谁?
  • php数组函数 菜鸟
  • 房地产企业销售额扣除土地价款
  • yii2关联查询
  • 什么情况下可以领取失业保险金
  • PHP基于什么语言
  • 营业外收入不算收入吗
  • php分类
  • 将外购商品用于捐赠的分录
  • 个人以实物出资怎么做账
  • 工会经费月月都缴纳吗?
  • 土地增值税采用
  • mysql动态表单设计与实现
  • 融资租赁公司的风险资产包括哪些
  • access怎么提取数据
  • mysql组合
  • 小规模纳税人企业所得税2023
  • 控股合并的账务处理
  • 车辆保险费如何提高
  • 初次购买金税盘怎么做账
  • 什么情况纳税
  • 物业电费加价如何处理
  • 收到电费发票做账怎么做
  • 支付原材料款项会计科目
  • 合伙企业对外投资收益怎么纳税
  • 收到增值税专用发票会计科目
  • 什么是流动负债确认条件是什么
  • 公司员工报销油费
  • 买辆车要交多少税
  • 做会计的步骤
  • mysql中的查询
  • MySQL创建数据库字符集和排序规则
  • mysql join 慢
  • mysql字段什么意思
  • mysql版本信息
  • vmware虚拟机不能识别iso
  • win7任务管理器怎么打开
  • xp任务栏靠右怎么调回来
  • tar解压工具
  • win8操作中心
  • linux系统有哪几个
  • win7屏幕刷新率怎么调高
  • shell脚本中如何交互传参
  • qq自动登出
  • javascript以及javascript的作用
  • 在全盘搜索以win
  • unity5用什么语言
  • js生成二维数组
  • javascript面向对象编程指南 pdf
  • jqgrid loadcomplete
  • 出口退的增值税怎么算
  • 出口退税备案单证目录
  • 浙江税务局网络发票页无法打字
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设