单源最短路径算法（对于非负权重）也称为 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) 是映射正实数的函数。如果对于任何实正常数 c，都存在一个整数常数 n0 ≤ 1 使得 f(n) > 0，则可以说函数 f(n) 为 o(g(n))。小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}大θ... 阅读更多

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