单源最短路径算法（对于非负权重）也称为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)在常数因子内的上界。我们写f(n) = O(g(n))，如果存在正常数n0和c使得在n0右侧f(n)总是位于或低于c*g(n)。O(g(n)) = { f(n) : 存在正常数c和n0使得0 ≤ f(n) ≤ c g(n)，对于所有n ≤ n0}阅读更多