单源最短路径算法（对于任意权重，正或负）也称为 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}大 Θ... 阅读更多