【数据结构与算法】TypeScript 实现图结构

class Grapg<T> {// 用于存储所有的顶点verteces: T[] = [];// 用于存储所有的边 采用邻接表的形式adjList: Map<T, T[]> = new Map();// 添加顶点addVertex(v: T) {this.verteces.push(v);// 初始化顶点的邻接表this.adjList.set(v, []);}// 添加边addEdge(v: T, w: T) {// 有向图 只需要添加单向的边this.adjList.get(v)?.push(w);// 无向图 需要添加反向的边this.adjList.get(w)?.push(v);}// 打印图printEdges() {// 遍历所有的顶点this.verteces.forEach((vertex) => {// 打印顶点和它的邻接表console.log(`${vertex} -> ${this.adjList.get(vertex)?.join(' ')}`);});}// 广度优先遍历BFS() {if (this.verteces.length === 0) return;const visited = new Set<T>(); // 用于存储已经访问过的顶点visited.add(this.verteces[0]); // 从第一个顶点开始遍历const queue = [this.verteces[0]]; // 用于存储待访问的顶点// 队列不为空时while (queue.length) {const v = queue.shift()!; // 取出队列的第一个顶点console.log(v); // 打印顶点const vEdges = this.adjList.get(v); // 获取该顶点的邻接表// 如果没有邻接表 则跳过if (!vEdges) continue;// 从前往后遍历for (const e of vEdges) {// 如果没有访问过 就入队列if (!visited.has(e)) {visited.add(e);queue.push(e);}}}}// 深度优先遍历DFS() {if (this.verteces.length === 0) return;const visited = new Set<T>(); // 用于存储已经访问过的顶点visited.add(this.verteces[0]); // 从第一个顶点开始遍历const stack = [this.verteces[0]]; // 用于存储待访问的顶点// 栈不为空时while (stack.length) {const v = stack.pop()!; // 取出栈顶的顶点console.log(v); // 打印顶点const vEdges = this.adjList.get(v); // 获取该顶点的邻接表if (!vEdges) return; // 如果没有邻接表 则跳过// 从后往前遍历for (let i = vEdges.length - 1; i >= 0; i--) {const e = vEdges[i]; // 获取顶点// 如果没有访问过 就入栈if (!visited.has(e)) {stack.push(e);visited.add(e);}}}}
}const graph = new Grapg<string>();
// 添加A-I的顶点
for (let i = 0; i < 9; i++) {graph.addVertex(String.fromCharCode(65 + i));
}
// 添加边
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');
graph.printEdges();
console.log('BFS');
graph.BFS();
console.log('DFS');
graph.DFS();

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

文心一言 VS 讯飞星火 VS chatgpt (68)-- 算法导论6.5 7题

文心一言 VS 讯飞星火 VS chatgpt &#xff08;68&#xff09;-- 算法导论6.5 7题 七、试说明如何使用优先队列来实现一个先进先出队列&#xff0c;以及如何使用优先队列来实现栈(队列和栈的定义见 10.1 节。) 文心一言&#xff1a; 优先队列是一种数据结构&#xff0c;其中…

无人机机巢有哪些,无人机机场/机场的主要分类

随着无人机技术的飞速发展&#xff0c;无人机已经渗透到了物流、农业、救援、公共安全等多个领域。而为了使这些无人机能更加高效、灵活地运行&#xff0c;一个新的概念应运而生&#xff0c;那就是无人机机巢&#xff08;UAV Nest&#xff09;。复亚智能无人机机巢是一种供无人…

GitLab备份升级

数据备份(默认的备份目录在/var/opt/gitlab/backups/下&#xff0c;生成一个以时间节点命名的tar包。) gitlab-rake gitlab:backup:create新建repo源&#xff0c;升级新版本的gitlab vim /etc/yum.repos.d/gitlab-ce.repo [gitlab-ce] namegitlab-ce baseurlhttps://mirrors.…

【大数据】-- docker 启动 mysql 5.7,开启 binlog

1.说明 mysql binlog&#xff1a;二进制日志文件。它有两个作用&#xff0c;一是增量备份&#xff0c;即只备份新增的内容&#xff0c;可以用于恢复数据&#xff1b;二是用于主从复制等&#xff0c;即主节点维护了一个binlog日志文件&#xff0c;从节点从binlog中同步数据。 …

嵌入式pc技术的特点有哪些?

嵌入式PC技术是将计算机硬件和软件嵌入到各种设备中的一种技术&#xff0c;它具有低功耗、高效率、小型化、易于集成等优点&#xff0c;广泛应用于工业自动化、医疗设备、电力、通信、家用电器、物联网等领域&#xff0c;成为新时代工业生产和社会生活必不可少的技术之一。 嵌入…

使用idea实现git操作大全(在项目开发中遇到的实际情况

使用idea实现git操作大全&#xff08;在项目开发中遇到的实际情况&#xff09; 1.安装git插件2.在开发中切记拉一个自己的分支 1.安装git插件 2.在开发中切记拉一个自己的分支 选中需要拉的分支&#xff0c;右键该分支&#xff0c;选中new breach from “分支”&#xff0c;点…

接口测试如何在json中引用mock变量

在测试接口的时候&#xff0c;有的接口需要测试随机传入大量数据&#xff0c;查看数据库是否正常&#xff0c;但是大量的随机数据全靠自己手写会很慢&#xff0c;而且是通过json传递的数据。 这里我们就可以使用mock生成随机变量&#xff0c;然后在json中引用mock变量 首先看…

Reinforcement Learning with Code 【Code 1. Tabular Q-learning】

Reinforcement Learning with Code 【Code 1. Tabular Q-learning】 This note records how the author begin to learn RL. Both theoretical understanding and code practice are presented. Many material are referenced such as ZhaoShiyu’s Mathematical Foundation o…

leetcode 135. 分发糖果

2023.8.1 这道题只从前向后遍历会出各种问题&#xff0c;所以最后决定向前向后各遍历一次。 先定义一个饼干数组biscuits&#xff0c;记录每个孩子的饼干数量&#xff0c;初始化每个孩子饼干数量为1。 然后从前向后遍历、从后向前遍历&#xff0c;使其满足“相邻两孩子评分更高…

前端Vue入门-day08-vant组件库

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 vant 组件库 安装 导入 全部导入 按需导入 浏览器配饰 Viewport 布局 Rem 布局适配 vant 组件库 …

NASM汇编

1. 前置知识 1. 汇编语言两种风格 intel&#xff1a;我们学的NASM就属于Intel风格AT&T&#xff1a;GCC后端工具默认使用这种风格&#xff0c;当然我们也可以加选项改成intel风格 2. 代码 1. 段分布 .text: 存放的是二进制机器码&#xff0c;只读.data: 存放有初始化的…

sublime配置less的一些坑(1)

仅在sublime的Install Package安装保存less报错 在sublime的Install Package安装less 打开sublime软件,按住CtrlShiftP组合键,弹出的界面中选择Install Package 选中后enter或者回车。等会弹出一个弹窗,大致意思是说你已经成功安装了package control。如果你在此之前已经安装了…

MySQL之深入InnoDB存储引擎——物理文件

文章目录 一、参数文件二、日志文件三、表结构定义文件四、InnoDB 存储引擎文件1、表空间文件2、重做日志文件 一、参数文件 当 MySQL 实例启动时&#xff0c;数据库会先去读一个配置参数文件&#xff0c;用来寻找数据库的各种文件所在位置以及指定某些初始化参数。在默认情况…

怎么才能远程控制笔记本电脑?

为什么选择AnyViewer远程控制软件&#xff1f; 为什么AnyViewer是远程控制笔记本电脑软件的首选&#xff1f;以下是选择AnyViewer成为笔记本电脑远程控制软件的主要因素。 跨平台能力 AnyViewer作为一款跨平台远程控制软件&#xff0c;不仅可以用于从一台Windows电…

【ARM Coresight 系列文章 2.4 - Coresight 寄存器:DEVARCH,DEVID, DEVTYPE】

文章目录 1.1 DEVARCH(device architecture register)1.2 DEVID(Device configuration Register)1.3 DEVTYPE(Device Type Identifier Register) 1.1 DEVARCH(device architecture register) DEVARCH 寄存器标识了coresight 组件的架构信息。 bits[31:21] 定义了组件架构&…

我对排序算法的理解

排序算法一直是一个很困惑我的问题&#xff0c;早在刚开始接触 数据结构的时候&#xff0c;这个地方就很让我不解。就是那种&#xff0c;总是感觉少了些什么的感觉。一开始&#xff0c;重新来过&#xff0c;认真来学习这一部分&#xff0c;也总是学着学着就把概念记住了。过了一…

【Mybatis】Mybatis架构简介

文章目录 1.整体架构图2. 基础支撑层2.1 类型转换模块2.2 日志模块2.3 反射工具模块2.4 Binding 模块2.5 数据源模块2.6缓存模块2.7 解析器模块2.8 事务管理模块 3. 核心处理层3.1 配置解析3.2 SQL 解析与 scripting 模块3.3 SQL 执行3.4 插件 4. 接口层 1.整体架构图 MyBatis…

Redis 数据库高可用

Redis 数据库的高可用 一.Redis 数据库的持久化 1.Redis 高可用概念 &#xff08;1&#xff09;在web服务器中&#xff0c;高可用是指服务器可以正常访问的时间&#xff0c;衡量的标准是在多长时间内可以提供正常服务&#xff08;99.9%、99.99%、99.999%等等&#xff09;。 …

2023年第四届“华数杯”数学建模思路 - 案例:随机森林

## 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 什么是随机森林&#xff1f; 随机森林属于 集成学习 中的 Bagging&#xff08;Bootstrap AGgregation 的简称&#xff09; 方法。如果用图来表示他们之…

【微信支付V3】

微信支付V3 微信支付V3 开发文档&#xff1a; https://pay.weixin.qq.com/wiki/doc/apiv3/wxpay/pages/index.shtml 1. 查看文档 使用微信提供的SDK&#xff0c;在文档中进入SDK 2. 开发 1. 添加jar包 <dependency><groupId>com.github.wechatpay-apiv3<…