单源最短路径算法（对于任意权重正或负）也称为 Bellman-Ford 算法，用于查找从源顶点到任何其他顶点的最小距离。该算法与 Dijkstra 算法的主要区别在于，在 Dijkstra 算法中，我们无法处理负权重，但在这里我们可以轻松地处理它。Bellman-Ford 算法以自底向上的方式查找距离。首先，它找到路径中只有一条边的那些距离。之后增加路径长度以找到所有可能的解决方案。输入 - 图的成本矩阵：0 6 ∞ 7 ∞ ∞ ... 阅读更多

单源最短路径算法（对于非负权重）也称为 Dijkstra 算法。给定一个图 G(V, E) 及其邻接矩阵表示，并提供一个源顶点。Dijkstra 算法用于查找从源顶点到图 G 的任何其他顶点的最小最短路径。从起始节点到任何其他节点，找到最小的距离。在此问题中，图使用邻接矩阵表示。（成本矩阵和邻接矩阵为此目的类似）。输入 - 邻接矩阵 - 0 3 6 ∞ ∞ ∞ ∞ 3 0 2 1 ∞ ∞ ... 阅读更多

给定一个连通图 G(V, E)，并且给出了每条边的权重或成本。Prim 算法将从图 G 中找到最小生成树。它是一种增长树方法。该算法需要一个种子值来启动树。种子顶点被扩展以形成整个树。问题将使用两个集合来解决。一个集合保存已选择的节点，另一个集合保存尚未考虑的项。从种子顶点开始，它根据最小边成本获取相邻顶点，因此它通过获取... 阅读更多

给定一个连通图 G(V, E)，并且给出了每条边的权重或成本。Kruskal 算法将使用图和成本找到最小生成树。它是一种合并树方法。最初存在不同的树，该算法将通过获取成本最小的那些边来合并它们，并形成一棵单一树。在此问题中，列出了所有边，并根据其成本进行排序。从列表中，取出成本最小的边并添加到树中，并且每次都会检查边是否形成循环，... 阅读更多

广度优先搜索 (BFS) 遍历是一种算法，用于访问给定图的所有节点。在此遍历算法中，选择一个节点，然后逐个访问所有相邻节点。完成所有相邻顶点后，它将进一步移动以检查另一个顶点并再次检查其相邻顶点。要实现此算法，我们需要使用队列数据结构。所有相邻顶点都添加到队列中，当所有相邻顶点完成后，从队列中删除一个项并开始遍历该... 阅读更多

深度优先搜索 (DFS) 是一种图遍历算法。在此算法中，给定一个起始顶点，并且当找到一个相邻顶点时，它首先移动到该相邻顶点并尝试以相同的方式遍历。它尽可能地遍历整个深度，之后它回溯以到达以前的顶点以找到新的路径。要以迭代方式实现 DFS，我们需要使用堆栈数据结构。如果我们想递归地执行它，则不需要外部堆栈，它可以使用内部堆栈进行递归调用。输入：邻接... 阅读更多

图是一种非线性数据结构。它使用节点表示数据，并使用边表示它们之间的关系。图 G 有两个部分。顶点和边。顶点用集合 V 表示，边用集合 E 表示。因此图表示法为 G(V, E)。让我们看一个例子来了解一下。在此图中，有五个顶点和五条边。这些边是有向的。例如，如果我们选择连接顶点 B 和 D 的边，则源顶点为 B，目标顶点为 D。因此我们可以从 B 移动到 D，但不能从... 阅读更多

均摊分析此分析用于偶尔的操作非常慢，但大多数执行非常频繁的操作都更快。在数据结构中，我们需要对哈希表、不相交集等进行均摊分析。在哈希表中，大多数情况下搜索时间复杂度为 O(1)，但有时它执行 O(n) 操作。当我们想要在哈希表中搜索或插入元素时，在大多数情况下，它是花费常数时间的任务，但是当发生冲突时，它需要 O(n) 次操作来解决冲突。聚合方法聚合方法用于... 阅读更多

小o记号除了大O、大Ω和大θ记号之外，还存在一些其他记号。小o记号就是其中之一。小o记号用于描述一个不能紧密的界限。换句话说，f(n) 的松散上界。设 f(n) 和 g(n) 是映射正实数的函数。我们可以说函数 f(n) 为 o(g(n))，如果对于任何实正常数 c，存在一个整数常数 n0 ≤ 1 使得 f(n) > 0。小o记号的数学关系使用数学关系，我们可以说 f(n) = o(g(n)) 意味着，示例... 阅读更多

渐进记号渐进记号用于表示算法在渐进分析中的复杂度。这些记号是表示复杂度的数学工具。三种常用的记号。大Ω记号大Ω (Ω) 记号给出了函数 f(n) 在常数因子内的下界。我们写 f(n) = Ω(g(n))，如果存在正常数 n0 和 c 使得，在 n0 的右侧，f(n) 始终位于或高于 c*g(n)。Ω(g(n)) = { f(n) : 存在正常数 c 和 n0 使得 0 ≤ c g(n) ≤ f(n)，对于所有 n ≤ n0}大θ... 阅读更多