霍夫曼编码(英语:Huffman Coding),又译为哈夫曼编码、赫夫曼编码,是一种用于无损数据压缩的熵编码(权编码)算法。由大卫·霍夫曼在1952年发明。熵用于信息量度量,其本质是信息的平均编码长度,所以也叫熵编码。...
平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. Landis发明了这棵树,所以它又叫AVL...
克鲁斯卡尔算法和普利姆算法一样,用于构建最小生成树。普利姆算法基本思想就是寻找每个顶点权值最小的边,而克鲁斯卡尔算法则是依据边来寻找权值最小的边。 1. 算法过程 上图的邻接矩阵表示如下: 由于克鲁斯卡尔算法是基于边来构...
生成树:如果对于图 G 中任意两个顶点 vi,vj 都是连通的,则称G是连通图。生成树是对连通图而言的,是连同图的极小连通子图,包含图中的所有顶点,有且仅有n-1条边。 最小生成树:在图论中,常常将树定义为一个无回路连通...
Floyd 算法(Floyd-Warshall algorithm)又称为弗洛伊德算法、插点法,用于在给定的加权图中计算两个顶点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题。该算法名称以创始人之一、19...
迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,它用于解决的是有向图中最短路径问题。Dijkstra 算法能够计算出给定起【起始顶点】到【其他所有顶点】的最短路径。 1. 算法过程 我们通过一个例子来分...
图的遍历和树的遍历类似,从图中某一顶点出发访问遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程叫做图的遍历。 由于图中的任何顶点都可能和其余所有的顶点相邻接,极有可能沿着某条路径搜索后,又回到原顶点,而有些顶点可能还...