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

Javascript数据结构——图Graph

当然,让我们深入探讨一下JavaScript中的图数据结构,并列出一些常见的面试题及其代码示例。

图数据结构详解

图(Graph)是一种非线性的数据结构,由节点(也称为顶点)和连接这些节点的边组成。节点可以表示实体(如人、地点、事物等),而边则表示这些实体之间的关系。图可以分为有向图和无向图:

  • 有向图(Directed Graph):边有方向,即从一个节点指向另一个节点。
  • 无向图(Undirected Graph):边没有方向,表示两个节点之间的连接。
图的表示方法
  1. 邻接矩阵(Adjacency Matrix)

    • 使用一个二维数组表示,如果节点i和节点j之间有边,则数组[i][j]为1(或边的权重),否则为0。
    • 优点:查找边是否存在很快(O(1))。
    • 缺点:空间复杂度较高,尤其是稀疏图(边的数量远小于节点对数量的图)。
  2. 邻接表(Adjacency List)

    • 使用一个数组或链表数组表示,每个节点对应一个链表,链表中存储该节点连接的所有节点。
    • 优点:空间复杂度较低,适合稀疏图。
    • 缺点:查找边是否存在的时间复杂度较高(O(V))。
图的遍历
  1. 深度优先搜索(DFS, Depth-First Search)

    • 使用栈(递归或显式栈)遍历节点,尽可能深入搜索每一个分支。
    • 可以用递归或迭代实现。
  2. 广度优先搜索(BFS, Breadth-First Search)

    • 使用队列逐层遍历节点。
    • 常用于寻找最短路径(在无权图中)。

常见面试题及其代码

  1. 判断图是否有环(DFS)
function hasCycle(graph) {const visited = new Set();const recursionStack = new Set();function dfs(node) {if (recursionStack.has(node)) return true;if (visited.has(node)) return false;visited.add(node);recursionStack.add(node);for (const neighbor of graph[node] || []) {if (dfs(neighbor)) return true;}recursionStack.delete(node);return false;}for (const node in graph) {if (dfs(node)) return true;}return false;
}
  1. 图的深度优先遍历(DFS)
function dfsTraversal(graph, start, visited = new Set()) {if (visited.has(start)) return;visited.add(start);console.log(start);for (const neighbor of graph[start] || []) {dfsTraversal(graph, neighbor, visited);}
}
  1. 图的广度优先遍历(BFS)
function bfsTraversal(graph, start) {const queue = [start];const visited = new Set();while (queue.length > 0) {const node = queue.shift();if (!visited.has(node)) {visited.add(node);console.log(node);for (const neighbor of graph[node] || []) {if (!visited.has(neighbor)) {queue.push(neighbor);}}}}
}
  1. 计算图的拓扑排序(Kahn’s Algorithm)
function topologicalSort(graph) {const inDegree = {};const result = [];const queue = [];// Initialize in-degree mapfor (const node in graph) {inDegree[node] = 0;}// Calculate in-degreesfor (const node in graph) {for (const neighbor of graph[node] || []) {inDegree[neighbor] = (inDegree[neighbor] || 0) + 1;}}// Enqueue nodes with zero in-degreefor (const node in inDegree) {if (inDegree[node] === 0) {queue.push(node);}}// Process nodeswhile (queue.length > 0) {const node = queue.shift();result.push(node);for (const neighbor of graph[node] || []) {inDegree[neighbor]--;if (inDegree[neighbor] === 0) {queue.push(neighbor);}}}// If there was a cycle, not all nodes would be visitedreturn result.length === Object.keys(graph).length ? result : [];
}
  1. 计算所有节点对之间的最短路径(Floyd-Warshall Algorithm)
function floydWarshall(graph) {const n = Object.keys(graph).length;const dist = JSON.parse(JSON.stringify(graph));for (let k = 0; k < n; k++) {for (let i = 0; i < n; i++) {for (let j = 0; j < n; j++) {if (dist[i][k] !== Infinity && dist[k][j] !== Infinity && dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}return dist;
}
  1. 检测二分图(Bipartite Graph)
function isBipartite(graph) {const colors = {};const queue = [];function bfs(node, color) {colors[node] = color;queue.push(node);while (queue.length > 0) {const currentNode = queue.shift();const currentColor = colors[currentNode];for (const neighbor of graph[currentNode] || []) {if (!colors[neighbor]) {colors[neighbor] = -currentColor;queue.push(neighbor);} else if (colors[neighbor] === currentColor) {return false;}}}return true;}for (const node in graph) {if (!colors[node]) {if (!bfs(node, 1)) {return false;}}}return true;
}
  1. 图的最小生成树(Prim’s Algorithm)
function primMST(graph) {const n = Object.keys(graph).length;const key = new Array(n).fill(Infinity);const parent = new Array(n).fill(-1);const inMST = new Array(n).fill(false);key[0] = 0;parent[0] = -1;for (let count = 0; count < n - 1; count++) {let u = -1, min = Infinity;for (let v = 0; v < n; v++) {if (!inMST[v] && key[v] < min) {u = v;min = key[v];}}inMST[u] = true;for (const v of graph[u] || []) {if (!inMST[v] && graph[u][v] < key[v]) {parent[v] = u;key[v] = graph[u][v];}}}// Construct MSTconst mst = [];for (let i = 1; i < n; i++) {mst.push([parent[i], i, graph[parent[i]][i]]);}return mst;
}
}

图的克鲁斯克尔算法(Kruskal’s Algorithm)

class UnionFind {constructor(n) {this.parent = new Array(n);for (let i = 0; i < n; i++) {this.parent[i] = i;}}find(u) {if (this.parent[u] !== u) {this.parent[u] = this.find(this.parent[u]); // 路径压缩,使得后续查找更快}return this.parent[u];}union(u, v) {let rootU = this.find(u);let rootV = this.find(v);if (rootU !== rootV) {this.parent[rootU] = rootV;}}
}function kruskalMST(graph) {// 图的表示:graph = [ [u, v, weight], ... ]let edges = graph.slice().sort((a, b) => a[2] - b[2]); // 排序边let n = new Set(); // 存储所有顶点for (let edge of edges) {n.add(edge[0]);n.add(edge[1]);}let uf = new UnionFind(n.size);let mst = [];let mstCost = 0;for (let edge of edges) {let u = edge[0];let v = edge[1];let weight = edge[2];if (uf.find(u) !== uf.find(v)) {uf.union(u, v);mst.push(edge);mstCost += weight;}}return {mst: mst,cost: mstCost};
}// 示例使用
let graph = [[0, 1, 10],[0, 2, 6],[0, 3, 5],[1, 3, 15],[2, 3, 4]
];let result = kruskalMST(graph);
console.log("Edges in MST:", result.mst);
console.log("Total cost of MST:", result.cost);

相关文章:

Javascript数据结构——图Graph

当然&#xff0c;让我们深入探讨一下JavaScript中的图数据结构&#xff0c;并列出一些常见的面试题及其代码示例。 图数据结构详解 图&#xff08;Graph&#xff09;是一种非线性的数据结构&#xff0c;由节点&#xff08;也称为顶点&#xff09;和连接这些节点的边组成。节点…...

搭建nginx文件服务器

方法一&#xff1a;通过docker方式搭建 1、创建一个nginx配置文件/etc/nginx/nginx.conf user nginx; worker_processes 1;error_log /var/log/nginx/error.log warn; pid /var/run/nginx.pid;events {worker_connections 1024; }http {include mime.types;default_typ…...

Ubuntu Server安装谷歌浏览器

背景 服务器上跑爬虫服务器需要安装谷歌浏览器 安装 wget https://dl.google.com/linux/direct/google-chrome-stable_current_amd64.deb### sudo apt install ./google-chrome-stable_current_amd64.deb...

Vue项目结构推荐(复杂国际化项目与一般项目结构)

Vue项目结构推荐 一、一般项目结构二、复杂国际化项目结构总结/建议 下面结构是基于Vue和TypeScript开发的项目结构下src包下的结构&#xff0c;若只用到vue与js。则去掉typescript部分的包即可。 一、一般项目结构 assets&#xff1a;存放静态资源&#xff0c;如图片、字体、样…...

hive-sql 连续登录五天的用户

with tmp as (select 梁牧泽 as uid, 2023-03-03 as dt union allselect 梁牧泽 as uid, 2023-03-04 as dt union allselect 梁牧泽 as uid, 2023-03-05 as dt union allselect 梁牧泽 as uid, 2023-03-07 as dt union allselect 梁牧泽 as uid, 2023-03-08 as dt union allsel…...

FPGA 4x4矩阵键盘 实现

1原理 FPGA(现场可编程门阵列)4x4矩阵键盘的实现原理主要基于行列扫描法,通过FPGA对键盘的扫描和识别,实现对键盘输入信号的采集和处理。以下是对FPGA 4x4矩阵键盘实现原理的详细解释: 一、矩阵键盘的基本原理 结构:4x4矩阵键盘由4行和4列组成,共16个按键。每个按键位…...

ruoyi开发学习

将若依框架中的若依元素删掉 1.删除主目录中的“若依官网”&#xff1a; 在后端项目中&#xff0c;idea里借助mysql管理工具&#xff0c;找到sys_menu数据表&#xff0c;双击打开&#xff0c;找到4 若依官网&#xff0c;选中点击减号&#xff0c;绿色上箭头刷新&#xff0c;删…...

MacBook_Xcode_Swift雨燕

Swift Swift Swift Swift是苹果公司开发的现代化编程语言&#xff0c; 专为Apple平台设计。其简洁语法、类型安全、Optionals处理、Playgrounds交互式环境、泛型编程、协议与扩展、闭包功能、枚举与关联值、结构体与类的高效内存管理、异步编程的async/await语法、Swift Packa…...

ABAQUS三维Voronoi晶体几何建模

材料晶体塑性理论与细观尺度上晶体几何模型相融合的模拟方法为探究材料在塑性变形过程中的行为机制以及晶体材料优化开辟了新途径。本案例演示在CAD软件内通过Voronoi建立晶体三维模型&#xff0c;并将模型导入到Abaqus CAE内&#xff0c;完成晶体材料的有限元建模。 在AutoC…...

.Net加密与Java互通

.Net加密与Java互通 文章目录 .Net加密与Java互通前言RSA生成私钥和公钥.net加密出数据传给Java端采用java方给出的公钥进行加密采用java方给出的私钥进行解密 .net 解密来自Java端的数据 AES带有向量的AES加密带有向量的AES解密无向量AES加密无向量AES解密 SM2(国密)SM2加密Sm…...

MySQL 06 章——多表查询

多表查询&#xff0c;也称为关联查询&#xff0c;是指两个表或多个表一起完成查询操作 前提条件&#xff0c;这些一起查询的表之间是有关系的&#xff08;一对一、一对多&#xff09;&#xff0c;它们之间一定是有关联字段的。这个关联字段可能建立了外键&#xff0c;也可能没…...

猴子吃桃.

本节通过学习解决一个有趣的问题来加深对递归的理解. 问题描述: 有一个猴子摘了桃子吃,第一天吃一半多一个,第二天吃第一天剩余的一半多一个,第三天吃第二天剩余的一半多一个..以此类推,当第n天时,恰好只剩下一个桃子.求猴子一共摘了多少桃子. 思路解析: 解读题目,第n天的桃子…...

游戏引擎学习第72天

无论如何&#xff0c;我们今天有一些调试工作要做&#xff0c;因为昨天做了一些修改&#xff0c;结果没有时间进行调试和处理。我们知道自己还有一些需要解决的问题&#xff0c;却没有及时完成&#xff0c;所以我们想继续进行这些调试。对我们来说&#xff0c;拖延调试工作总是…...

element-ui dialog 组件源码分享

简单分享 dialog 组件源码&#xff0c;主要从以下三个方面&#xff1a; 1、dialog 页面结构。 2、dialog 组件属性。 3、dialog 组件挂载。 4、dialog 组件事件。 一、dialog 页面结构&#xff1a; 二、组件属性&#xff1a; 2.1 visible 是否显示 Dialog&#xff0c;支持…...

unity开发之shader 管道介质流动特效

效果 shader graph 如果出现下面的效果&#xff0c;那是因为你模型的问题&#xff0c;建模做贴图的时候没有设置好UV映射&#xff0c;只需重新设置下映射即可...

人工智能之机器学习算法

所有的机器学习算法都是要优化的&#xff0c;优化的必要条件是确定优化的目标函数(损失函数)&#xff0c;目标函数是根据实际问题(数据)转成的数学公式。 一.线性回归原理推导 &#xff08;1&#xff09;回归问题概述 在机器学习的有监督算法中&#xff0c;分类与回归二种情…...

Android布局layout的draw简洁clipPath实现圆角矩形布局,Kotlin

Android布局layout的draw简洁clipPath实现圆角矩形布局&#xff0c;Kotlin 通常&#xff0c;如果要把一个相对布局&#xff0c;FrameLayout&#xff0c;或者线性布局等这样的布局变成具有圆角或者圆形的布局&#xff0c;需要增加一个style&#xff0c;给它设置圆角&#xff0c;…...

信息系统常见的系统架构

1.1单文件架构 现在很多企业内部虽然已经建设了一些信息系统&#xff0c;但还是有不少业务没有用专门的信息系统管理起来&#xff0c;普遍都是采用Excel表格来实现这些业务数据的填报和查询统计。Excel就是属单文件架构&#xff0c;这种架构是指整个系统就是一个文件&#xff0…...

AngularJS 过滤器:提升用户体验的数据处理利器

AngularJS 过滤器:提升用户体验的数据处理利器 AngularJS,作为一款由Google维护的开源JavaScript框架,以其独特的双向数据绑定和MVVM(Model-View-ViewModel)架构在Web应用开发领域占据着重要地位。其中,AngularJS的过滤器(Filters)功能,为开发者提供了一种轻量级、高…...

Upload-labs 第四关(学习记录)

上传.htaccess文件 SetHandler application/x-httpd-php <IfModule mime_module> SetHandler application/x-httpd-php #在当前目录下&#xff0c;所有文件都会被解析成php代码执行 </IfModule> 上传一句话木马 保存为 1.png 文件 成功解析...

AI智能体架构设计:从成本黑洞到价值引擎的解耦之道

1. 从成本黑洞到价值引擎&#xff1a;为什么你的AI智能体架构正在吞噬预算又到了季度技术复盘会&#xff0c;财务那边递过来的云账单和工程人力成本&#xff0c;是不是又让你倒吸一口凉气&#xff1f;你看着报表上那个名为“AI智能体平台”的项目&#xff0c;它的资源消耗曲线几…...

小说下载器终极指南:一站式解决100+网站小说保存难题

小说下载器终极指南&#xff1a;一站式解决100网站小说保存难题 【免费下载链接】novel-downloader 一个可扩展的通用型小说下载器。 项目地址: https://gitcode.com/gh_mirrors/no/novel-downloader 在数字阅读时代&#xff0c;你是否曾因小说突然下架、网站404或网络中…...

Kerberos身份认证原理与企业级排错实战指南

1. 这不是“另一个登录框”&#xff0c;而是一套精密运转的身份验证齿轮系统很多人第一次听说 Kerberos&#xff0c;是在公司内网登录邮箱或访问内部系统时&#xff0c;看到那个带小盾牌图标的弹窗——“正在使用 Kerberos 协议进行身份验证”。于是下意识觉得&#xff1a;“哦…...

ARM指令追踪技术及TRCVICTLR寄存器详解

1. ARM指令追踪技术概述在嵌入式系统开发和调试过程中&#xff0c;指令追踪&#xff08;Instruction Trace&#xff09;是一项至关重要的技术。它通过硬件机制记录处理器的执行流程&#xff0c;为开发者提供程序运行的完整轨迹。ARM架构从v7开始引入嵌入式跟踪宏单元&#xff0…...

零基础轻松拿捏!魔珐星云青少年健康运动教学数字人搭建全流程指南

大家好&#xff01;本次给大家分享一款面向青少年体育教育的AI创意实践项目——青少年健康运动教学智能数字交互系统。本项目聚焦青少年体质健康痛点&#xff0c;围绕体育教学智能化升级需求&#xff0c;打造集健康知识教学、运动动作陪练、健康知识考核、运动能力评测于一体的…...

ARM PMU外部接口与性能监控寄存器详解

1. ARM性能监控寄存器外部接口深度解析性能监控单元(PMU)是现代处理器架构中用于硬件性能分析的核心模块&#xff0c;它通过一组可编程计数器实时捕获处理器微架构层面的各类事件。在ARMv8/v9架构中&#xff0c;PMU不仅可以通过系统寄存器访问&#xff0c;还提供了标准化的外部…...

DeepSeek基准测试避坑手册:92%开发者忽略的4大陷阱——硬件配置偏差、tokenizer不一致、batch size幻觉、温度值污染

更多请点击&#xff1a; https://codechina.net 第一章&#xff1a;DeepSeek基准测试避坑手册&#xff1a;92%开发者忽略的4大陷阱——硬件配置偏差、tokenizer不一致、batch size幻觉、温度值污染 硬件配置偏差&#xff1a;GPU显存与计算精度的隐性干扰 在A100&#xff08;8…...

Java数组工具类实战:设计不可实例化的静态工具类

实现一个工具类 MathUtils&#xff0c;满足以下要求&#xff1a; 1. 所有方法均为静态&#xff0c;且该类不能从外部实例化&#xff08;提示&#xff1a;使用私有构造器&#xff09;。 2. 提供三个静态方法&#xff1a;- maxArray(int[] arr)&#xff1a;返回较大值&#xff1b…...

串口通信粘包问题:成因深度解析与项目实战解决方案

在嵌入式开发、工业工控、上位机下位机交互项目中&#xff0c;串口&#xff08;RS232/RS485&#xff09;是最基础、最常用的通信方式。绝大多数开发者都遇到过这样的问题&#xff1a;串口接收的数据偶尔错乱、解析报错、数据拼接异常&#xff0c;单次接收的数据时而半包、时而多…...

销售怎么通过各种方法获取电话号码

第一种就是那个用爬虫电话号码&#xff0c;然后再打电话给客户。第二种是在别人的挪车电话看车挪车电话&#xff0c;然后再打电话找客户。第三就是。扫楼一顿顿的扫&#xff0c;第四就是这个那种商店&#xff0c;一个个的去问陌拜地推一个个的问店子要不要贷款&#xff0c;去问…...