最小生成树和哈夫曼树有什么区别？

Question

如题所述

Answer 1

最短路径和最小生成树是不同的概念.
最短路径是对于一个图的两个结点而言的.在一个图中,结点A通过某些结点和边可以走到结点B,那这些结点和边就组成一条A到B的路径,A到B的最短路径就是A到B的所有路径中边权值总和最小的那一条（或多条）.
最小生成树是对于一个图本身而言的.对于一个有n个结点的无向连通图（边没有方向,任意两点之间都存在路径可以到达）,必然可以去掉某些边,使得最终剩下n-1条边,并且n个结点仍然是连通的,这n个结点和n-1条边组成了原图的一个生成树,而最小生成树就是所有可能的生成树中n-1条边的权值总和最小的那一个（或多个）.
最短路径常用算法有：floyd,dijkstra,SPFA,A*等
最小生成树常用算法有：prim,kruskal

Answer 2

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。
最小生成树是计算连通图，连同各个节点的权值和最小的情况，有两种算法：prim和Kruskal。
哈夫曼树是用来进行编码压缩等，最小生成树用来设计水管、电路等连接各个结点所需的最短距离等用途。本回答被网友采纳

Answer 3

首先要搞清两者的定义。最小生成树是连通带权图G的权之和最小的生成树；哈夫曼树是给定N个权值作为N个叶子结点，构造一棵二叉树，使该树的带权路径长度达到最小。
最小生成树是在给定图G的基础上，进行构造。而哈夫曼树是给定权值按照一定要求构造。
因此，两者的应用也不相同。最小生成树多用于给定工程图后寻求最优解，而哈夫曼树则用于哈夫曼编码等。