为算法找到 510 篇 文章

赫夫曼编码

Arnab Chakraborty
更新于 2019 年 8 月 5 日 07:44:26

8K+ 次浏览

赫夫曼编码是无损数据压缩算法。在此算法中,为輸入的不同字符分配一个变长码。码长与字符的出现频率相关。出现频率最高的字符具有最小的码,出现频率最低的字符具有最长的码。主要分为两部分。第一部分是创建赫夫曼树,另一部分是遍历树以查找码。例如,考虑某些字符串“YYYZXXYYX”,字符 Y 的出现频率高于 X,字符 Z 的出现频率最低。因此,Y 的码长小于 X,X 的码长最长 ... 了解更多

所有对最短路径

Arnab Chakraborty
更新于 2023 年 11 月 7 日 03:20:32

70K+ 次浏览

所有对最短路径算法也称为弗洛伊德-沃尔舍尔算法,用于根据给定的加权图中所有对的最短路径问题。作为此算法的结果,它将生成一个矩阵,该矩阵将表示图中任何节点到所有其他节点的最小距离。最初,输出矩阵与给定的图成本矩阵相同。之后,输出矩阵将通过将所有顶点 k 更新为中间顶点来更新。此算法的时间复杂度为 O(V3),其中 V 是图中的顶点数。输入 − ... 了解更多

单源最短路径,任意权重

Arnab Chakraborty
2020 年 7 月 2 日 12:59:46 更新

浏览量 9K+

针对任意正负权重的单源最短路径算法(也称为 Bellman-Ford 算法)用于查找从源顶点到任何其他顶点的最短距离。此算法与 Dijkstra 算法的主要区别在于,Dijkstra 算法无法处理负权重,但此算法可以轻松处理。Bellman-Ford 算法采用自下而上的方式查找距离。它首先查找路径中仅含有一个边的距离。之后,增加路径长度以查找所有可能的解决方案。输入 − 图形的成本矩阵:0 6 ∞ 7 ∞ ∞ ... 阅读更多

单源最短路径,非负权重

Arnab Chakraborty
2020 年 7 月 2 日 13:00:42 更新

浏览量 725

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

Prim(最小生成树)MST 算法

Arnab Chakraborty
2020 年 7 月 2 日 13:02:11 更新

浏览量 967

有一个连通图 G(V, E),并且给定每条边的权重或成本。Prim 算法将从图 G 中找到最小生成树。它采用生长树方法。此算法需要一个种子值来启动树。种子顶点可以增长为一棵完整的树。此问题将使用两个集合来解决。一个集合包含已经选择的节点,另一个集合包含尚未考虑的项目。从种子顶点开始,它基于最小边成本找出相邻顶点,然后通过取出边缘来发展树 ... 阅读更多

Kruskal(最小生成树)MST 算法

Arnab Chakraborty
2020 年 6 月 11 日 19:45:15 更新

浏览量 1K+

有一个连通图 G(V, E),并且给定每条边的权重或成本。Kruskal 算法将使用图和成本找出最小生成树。它采用合并树的方法。最初有不同的树,此算法将合并这些树,方法是取出成本最低的那些边,并形成一棵树。在此问题中,将列出所有边并按照其成本排序。从列表中取出成本最低的边,并将其添加到树中,并且每次都会检查边是否形成回路,... 阅读更多

图的广度优先搜索或 BFS

Arnab Chakraborty
2019 年 8 月 5 日 06:55:55 更新

浏览量 2K+

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

图的深度优先搜索或 DFS

Arnab Chakraborty
更新于 2019 年 8 月 5 日 06:50:03

912 次观看

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

图及其表示

Arnab Chakraborty
更新于 2019 年 8 月 5 日 06:43:27

7K+ 次观看

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

摊销复杂度

Arnab Chakraborty
更新于 2019 年 8 月 5 日 06:38:15

3K+ 次观看

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

广告宣传