找到 1861 篇文章 关于数据结构

检查字符是否仅作为单个连续子字符串出现

Shubham Vora
更新于 2023年7月17日 12:02:34

148 次浏览

在本问题中,我们将检查给定字符串中所有字符是否连续出现。我们将使用 map 数据结构来解决问题。map 将跟踪特定字符的最后一个索引,并根据当前字符的最后一个索引,我们将决定字符串是否包含连续字符。问题陈述 - 我们给定一个长度为 N 的字符串 alpha,其中包含小写和大写字母字符。我们需要检查给定的字符串是否连续。只有当字符串包含所有字符作为... 阅读更多

不使用队列的广度优先搜索

Ayush Singh
更新于 2023年7月17日 10:06:09

417 次浏览

广度优先搜索 (BFS) 是一种图遍历算法,用于以广度方向遍历图中的节点。BFS 的典型实现使用队列数据结构来跟踪要访问的节点。但是,可以通过使用其他数据结构来实现 BFS,而无需使用显式队列。一种不使用队列实现 BFS 的替代方法是使用两个数组或列表:一个用于当前正在遍历的节点层,另一个用于下一层要遍历的节点。最初,当前层... 阅读更多

图中从源 S 到目标 D 且恰好有 K 条边的最短路径,用于多个查询

Ayush Singh
更新于 2023年7月17日 11:54:14

447 次浏览

在图中找到从源顶点到目标顶点且恰好有 K 条边的最短路径是最常见的图遍历问题之一。目标是找到具有最小权重且恰好有 K 条边的最短路径。此问题可能出现在许多实际上下文中,包括交通网络、路由协议和资源分配。动态规划 (DP) 和 Dijkstra 算法只是可以用来解决此问题的一些策略。可以使用多种方法找到给定约束条件下的最短路径。Dijkstra 算法... 阅读更多

对图着色所需的最小颜色数

Ayush Singh
更新于 2023年7月17日 11:52:55

705 次浏览

对图着色所需的最小颜色数是一个基本图论问题,它涉及对顶点着色,以使任何两个相邻的顶点都不具有相同的颜色。确定有效着色所需的最小颜色数。贪婪着色是一种简单且常用的技术,它根据顶点的邻居依次对顶点着色。回溯也仔细分析所有颜色分配。基于 DSatur 的图着色优先考虑度数和饱和度最高的顶点。使用的方法 贪婪着色 回溯 图着色 贪婪着色方法 贪婪着色技术使图着色变得容易。它对... 阅读更多

反转边以使每对节点之间存在路径的最小成本

Ayush Singh
更新于 2023年7月14日 10:51:33

243 次浏览

为了使每对节点之间存在路径而反转边的最小成本是指找到更改图中边方向的最低成本方法。目标是确保图中可以相互连接任何两个节点。这可能涉及更改一些边的方向以建立连接。最低成本代表与反转边相关的最小累积权重。通过最小化成本,我们可以实现具有所有节点对之间路径的指定结果... 阅读更多

形成环的边不具有相同颜色的所需最小颜色数

Ayush Singh
更新于 2023年7月14日 10:48:59

67 次浏览

为了减少所需的颜色数量,并避免形成环的边具有相同的颜色,可以使用图着色方法。目标是将颜色映射到顶点,使得由边连接的任何两个相邻顶点都不具有相同的颜色。通过识别图中的环,我们可以确保形成环的边分配不同的颜色。这需要使用深度优先搜索 (DFS) 或广度优先搜索 (BFS) 等策略遍历图,并在必要时应用回溯以回溯并重新分配颜色。目标是发现... 阅读更多

N 顶点图可以具有的最大边数,使得图是无三角形的 | Mantel 定理

Ayush Singh
更新于 2023年7月14日 10:46:59

152 次浏览

无三角形图的概念,其中任何三个顶点的集合都不会形成三角形,对于图论的研究至关重要。考虑一个 N 顶点图可以有多少条边并且仍然是无三角形图,这很有趣。Mantel 定理为这个问题提供了优雅的解决方案。Mantel 定理可以确定图中没有生成任何三角形的最大边数。使用的方法 Mantel 算法 Mantel 算法 Mantel 定理是图论中的一个著名结论,它阐明了无三角形图可以有多少条边。根据该定理,... 阅读更多

图中最远节点的距离的最小值

Ayush Singh
更新于 2023年7月14日 10:45:28

274 次浏览

这里的目标是确定从给定起点到整个图的终点的最少跳数路径。可以使用多种方法计算此距离,包括专门为图遍历(如广度优先搜索)和最短路径发现(如 Dijkstra 算法)设计的那些方法。使用的方法 广度优先搜索 Dijkstra 算法 广度优先搜索方法 使用广度优先搜索算法遍历所有图顶点。在移至下一阶段之前,会访问源节点的所有邻居。在无权图中,BFS 确定最短路径。通过应用 BFS... 阅读更多

使用优先队列和数组列表的最小生成树

Ayush Singh
更新于 2023年7月14日 10:44:04

467 次浏览

为了发现图的最小生成树,准备使用优先队列和数组列表的组合。首先,我们用图的边初始化优先队列,按其权重升序排序。然后,我们创建一个数组列表来存储最小生成树的边。我们反复从优先队列中提取权重最小的边,并检查将其包含在数组列表中是否会形成环。如果不是,我们将边... 阅读更多

需要添加以形成三角形的最小边数

Ayush Singh
更新于 2023年7月14日 10:41:16

56 次浏览

为了确定在图中形成三角形所需的最小边数,我们分析了节点之间的网络。在三个节点通过边直接或间接连接的情况下,可以形成三角形。所需的最小边数等于三个节点之间现有连接中丢失的边数。通过查看图形并区分未连接的节点,我们可以计算形成三角形所需的额外边数。这种方法有所作为,因为它需要最少的... 阅读更多

广告