图:广度优先遍历(BFS)和深度优先遍历(DFS)

1.工具类:队列和字典

export class DictionNary {
    // 字典的封装
    constructor() {
        this.items = {}
    }
    set(key, value) {
        // 添加键
        this.items[key] = value
    }
    has(key){
        // 判断键是否存在
        return this.items.hasOwnProperty(key)
    }
    get(key){
        // 获取键的value
        return this.has(key) ? this.items[key] : undefined
    }
    remove (key){
        // 删除键
        if(this.has(key)){
            delete this.items[key]
            return true
        }
        return false
    }
    keys(){
        // 获取所有的键
        return Object.keys(this.items)
    }
    values(){
        // 获取所有的值
        return Object
    }
    size(){
        // 获取键值对的数量
        return this.keys().length
    }
    clear(){
        // 清空字典
        this.items = {}
    }
    toString(){
        // 转换为字符串
        if(this.size() > 0){
            let objString = `{${this.keys().join(',')}}`
            return objString
        }else{
            return '{}'
        }
    }
}

export class Queue {
    // 队列的封装
    constructor() {
        this.items = []
    }
    // 方法
    enqueue(element) {
        // 添加元素到队列
        this.items.push(element)
    }
    dequeue() {
        // 移除队列的第一个元素
        return this.items.shift()
    }
    front() {
        // 返回队列的第一个元素
        return this.items[0]
    }
    isEmpty() {
        // 判断队列是否为空
        return this.items.length == 0
    }
    size() {
        // 返回队列的元素个数
        return this.items.length
    }
    toString() {
        return this.items.toString()
    }
    
}

2. 图的封装

class Graph {
        constructor() {
            // 顶点
            this.vertexes = []
            // 边
            this.edges = new DictionNary()
        }
        // 方法
        addVertex(v){
            // 添加顶点
            this.vertexes.push(v)
            // 顶点对于边数组的初始化
            this.edges.set(v, [])
        }
        addEdge(v1, v2){
            // 无向图中边的设置
            this.edges.get(v1).push(v2)
            this.edges.get(v2).push(v1)
        }
        toString(){
            let result = ''
            for(let i = 0; i < this.vertexes.length; i++){
                result += this.vertexes[i] + ' -> '
                const neighbors = this.edges.get(this.vertexes[i])
                for(let j = 0; j < neighbors.length; j++){
                    result += neighbors[j] + ' '
                }
                result += '\n'
            }
            return result
        }
        initializeColor(){
            // 顶点遍历颜色初始化
            const colors = []
            for(let i = 0; i < this.vertexes.length; i++){
                colors[this.vertexes[i]] = 'white'
            }
            return colors
        }
        
        bfs(firstVertex, callback){
            // 广度优先遍历
            // 顶点遍历测试
            // 1.层序遍历:Breadth-First Search (BFS)
            // 2.深度遍历:Depth-First Search (DFS)
            // 3.为了记录顶点是否被访问过,我们使用三种颜色定义顶点的状态
                // 1.白色:表示该顶点还没有被访问
                // 2.灰色:表示该顶点被访问过,但并未被探索(被探索意思是其所有相邻顶点都被访问过)
                // 3.黑色:表示该顶点被访问过且被完全探索
            // 1.初始化顶点颜色
           const colors = this.initializeColor()
           // 2.创建队列
           const queue = new Queue()
           // 3.将第一个顶点加入队列
           queue.enqueue(firstVertex)
           // 4.循环遍历队列
           while(!queue.isEmpty()){
            // 4.1.从队列中取出一个顶点
               const v = queue.dequeue()
               // 4.2.获取和该顶点相邻的顶点
               const neighbors = this.edges.get(v)
               // 4.3.将当前顶点的颜色设置为灰色(被访问过)   
               colors[v] = 'gray'
               // 4.4.遍历该顶点的所有相邻顶点
               for(let i = 0; i < neighbors.length; i++){
                   const w = neighbors[i]
                   if(colors[w] === 'white'){
                       colors[w] = 'gray'
                       queue.enqueue(w) 
                   }
               }
               // 4.5.将当前顶点设置为黑色(被探索)
               colors[v] = 'black'
               // 4.6.调用callback函数
               callback(v)
           }
        }

        dfs(initVertex, callback){
            // 1.初始化颜色
            const colors = this.initializeColor()
            // 2.递归函数
            this.dfsVisit(initVertex, colors, callback)
            
        }
        dfsVisit(vertexes, colors, callback){
            // 1.访问过节点置灰色
            colors[vertexes] = 'gray'
            // 2.调用callback函数
            callback(vertexes)
            // 3.获取和该顶点相邻的顶点
            const neighbors = this.edges.get(vertexes)
            for(let i = 0; i < neighbors.length; i++){
                const w = neighbors[i]
                if(colors[w] === 'white'){
                    this.dfsVisit(w, colors, callback)
                }
            }
            // 4.访问完节点置黑色
            colors[vertexes] = 'black'
        }

    }

图测试用例

在这里插入图片描述

 const graph = new Graph()
    // 1.添加顶点
    const myVertices = ['A', 'B', 'C', 'D', 'E', 'F','G', 'H','I']
    for(let i = 0; i < myVertices.length; i++){
        graph.addVertex(myVertices[i])
    }
    // 2.添加边
    graph.addEdge('A', 'B')
    graph.addEdge('A', 'C')
    graph.addEdge('A', 'D')
    graph.addEdge('C', 'D')
    graph.addEdge('C', 'G')
    graph.addEdge('D', 'G')
    graph.addEdge('D', 'H')
    graph.addEdge('B', 'E')
    graph.addEdge('B', 'F')
    graph.addEdge('E', 'I')

    console.log(graph.toString())
    
    // 测试广度优先遍历
    let result = ''
    graph.bfs(graph.vertexes[0], function(v){
        result += v + ' '
    })
    console.log(result)

    // 测试深度优先遍历
    let deepRsult = ''
    graph.dfs(graph.vertexes[0], function(v){
        deepRsult += v + ' '
    })
    console.log(deepRsult)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/606323.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

利用github pages建立Serverless个人博客

利用github pages建立Serverless个人博客 概述 使用github pages&#xff0c;可以在github上部署静态网站。利用这个功能&#xff0c;可以很方便地实现个人博客的发布托管。 比如我的个人博客&#xff1a;Buttering’s Blog 对应代码仓库&#xff1a;buttering/EasyBlog: 自…

MT3516W-ASEMI工业电源专用MT3516W

编辑&#xff1a;ll MT3516W-ASEMI工业电源专用MT3516W 型号&#xff1a;MT3516W 品牌&#xff1a;ASEMI 封装&#xff1a;MTW-5 最大重复峰值反向电压&#xff1a;1600V 最大正向平均整流电流(Vdss)&#xff1a;35A 功率(Pd)&#xff1a;大功率 芯片个数&#xff1a;5…

程序员不会告诉老板的那些神器

目录 1. 持续集成工具&#xff1a;CruiseControl&#xff08;简称CC&#xff09; 2. 代码风格、质量检查工具&#xff1a;StyleCop 3.AI工具 3.1 AI助力编写开发日报 3.2 AI助力编写普适性代码 3.3 AI助力生成代码注释 3.4 AI助力重构代码去掉“坏味道” 3.5 AI助力…

汽车品牌区域营销方案

领克汽车粤海区域营销方案-36P 活动策划信息&#xff1a; 方案页码&#xff1a;36页 文件格式&#xff1a;PPT 方案简介&#xff1a; 车市反弹形势明显&#xff0c;领克销量呈现稳健上涨趋势 品牌 未来市场可观&#xff0c;应 持续扩大品牌声量&#xff0c;保持市场占有优…

【C++】C++11--- lambda表达式

目录 Lambda表达式概述 Lambda表达式语法定义 Lambda表达式参数详解 Lambda捕获列表 捕获列表总结 Lambda参数列表 可变规则mutable lambda表达式原理 Lambda表达式概述 当对自定义类型的数据集合进行排序时&#xff0c;需要根据自定义类型的不同属性去实现不同的排序方…

ESD静电问题 | 手持摄像头整改

【转自微信公众号&#xff1a;柯普伦科技】

用webui.sh安装报错No module named ‘importlib.metadata‘

安装sdweb报错&#xff0c;出现No module named importlib.metadata&#xff1a; glibc version is 2.35 Cannot locate TCMalloc. Do you have tcmalloc or google-perftool installed on your system? (improves CPU memory usage) Traceback (most recent call last):File…

访问网络附加存储:nfs

文章目录 访问网络附加存储一、网络附加存储1.1、存储类型1.3、通过NFS挂载NAS1.4、NFS挂载过程服务端客户端 二、实验&#xff1a;搭建NFS服务端及挂载到nfs客户端服务端客户端测试命令合集服务端客户端 访问网络附加存储 一、网络附加存储 1.1、存储类型 DAS&#xff1a;Di…

TCP四次挥手中为什么 TIME_WAIT 等待的时间是 2MSL?

TCP 连接断开 1、TCP 四次挥手过程是怎样的&#xff1f;如下图 2、为什么 TIME_WAIT 等待的时间是 2MSL&#xff1f; MSL 是 Maximum Segment Lifetime&#xff0c;报文最大生存时间&#xff0c;它是任何报文在网络上存在的最长时间&#xff0c;超过这个时间报文将被丢弃。因…

激光雷达技术:科技之眼,照亮前行

在科技与人文关怀的交响乐章中&#xff0c;一项名为“蝙蝠避障”使用了激光雷达技术原理及应用的创新成果&#xff0c;正悄然改变着视障朋友们的生活方式&#xff0c;为他们的日常出行铺设了一条充满希望的光明之路。今天&#xff0c;让我们一起深入探讨这项技术如何成为盲人出…

毕业论文怎么写? 推荐4个AI工具

写作这件事一直让我们从小学时期就开始头痛&#xff0c;初高中时期800字的作文让我们焦头烂额&#xff0c;一篇作文里用尽了口水话&#xff0c;拼拼凑凑才勉强完成。 大学时期以为可以轻松顺利毕业&#xff0c;结果毕业前的最后一道坎拦住我们的是毕业论文&#xff0c;这玩意不…

微火快讯:全域运营服务商是什么?赚得多吗?

随着互联网下半场的开启&#xff0c;公域和私域两大流量池持续不断地迸发出新的活力&#xff0c;一定程度上推动了全域运营赛道和微火全域运营服务商职业的兴起。 所谓全域运营&#xff0c;简而言之&#xff0c;就是所有领域内与商家、品牌运营相关的业务&#xff0c;包括但不限…

Tomcat、MySQL、Redis最大支持说明

文章目录 一、Tomcat二、MySQL三、Redis1、最大连接数2、TPS、QPS3、key和value最大支持 一、Tomcat 查看SpringBoot内置Tomcat的源码&#xff0c;如下&#xff1a; 主要就是看抽象类AbstractEndpoint&#xff0c;可以看到默认的核心线程数10&#xff0c;最大线程数200 通过…

Linux|了解如何使用 awk 内置变量

引言 当我们揭开 Awk 功能部分时&#xff0c;我们将介绍 Awk 中内置变量的概念。您可以在 Awk 中使用两种类型的变量&#xff1a;用户定义的变量和内置变量。 内置变量的值已经在 Awk 中定义&#xff0c;但我们也可以仔细更改这些值&#xff0c;内置变量包括&#xff1a; FILEN…

实时路况信息获取的意义:点亮盲人前行的每一寸道路

在这个日新月异的科技时代&#xff0c;一款名为“蝙蝠避障”的创新应用正以温暖而坚定的步伐&#xff0c;为盲人朋友们的日常出行编织着安全与自由的网络。这款应用的核心——激光雷达技术&#xff0c;正以前所未有的方式&#xff0c;重新定义着实时路况信息获取的意义&#xf…

第二证券午评:沪指涨近1%,地产、半导体等板块拉升,锂电池概念活跃

9日早盘&#xff0c;两市股指全线走高&#xff0c;沪指涨近1%&#xff0c;创业板指大涨近2%&#xff1b;北向资金大举出场扫货&#xff0c;半日净买入超100亿元。 到午间收盘&#xff0c;沪指涨0.91%报3156.96点&#xff0c;深成指涨1.63%&#xff0c;创业板指涨1.85%&#xf…

【基于 PyTorch 的 Python深度学习】5 机器学习基础(2)

前言 文章性质&#xff1a;学习笔记 &#x1f4d6; 学习资料&#xff1a;吴茂贵《 Python 深度学习基于 PyTorch ( 第 2 版 ) 》【ISBN】978-7-111-71880-2 主要内容&#xff1a;根据学习资料撰写的学习笔记&#xff0c;该篇主要介绍了如何选择合适的激活函数、损失函数和优化器…

学习大数据,所需更要的shell基础(2)

文章目录 read读取控制台输入函数系统函数bashnamedirname 自定义函数Shell工具&#xff08;重点&#xff09;cutawk 正则表达式入门常规匹配常用特殊字符 read读取控制台输入 1&#xff09;基本语法 read (选项) (参数) ①选项&#xff1a; -p&#xff1a;指定读取值时的提示…

【福利】思科CCNP考试介绍(附CCNP题库下载)

网络行业有两个大神级别的证书&#xff1a;思科认证和华为认证&#xff0c;目前相比思科认证&#xff0c;华为认证在国内更加吃香哦&#xff0c;如果你在国内就业或发展考虑建议考华为的。不过还是有少部分在外企或有出国计划的IT人员考思科的。 那今天小微就来给大家介绍下思科…

SpringBoot启动流程源码解析

目录 一、SpringApplication构造方法解析 1. web应用类型 2. BootstrapRegistryInitializer 3. ApplicationContextInitializer 4. ApplicationListener 5. 推断Main方法所在类 二、SpringApplication.run(String... args)方法解析 1.创建DefaultBootstrapContext 2.获…