算法笔记——【贪心算法】哈夫曼编码问题

软件02 1311611006 张松彬利用贪心算法构造哈夫曼树及输出对应的哈夫曼编码问题简述：两路合并最佳模式的贪心算法主要思想如下：（1）设w={w0,w1,......wn-1}是一组权值，以每个权值作为根结点值，构造n棵只有根的二叉树（2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和（3）重复（2），直到合并成一颗二叉树为一、实验目的（1）了解贪心算法和哈夫曼树的定义（2）掌握贪心法的设计思想并能熟练运用（3）设计贪心算法求解哈夫曼树（4）设计测试数据，写出程序文档二、实验内容（1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树（2）设计函数，先序遍历输出哈夫曼树各结点3)设计函数，按树形输出哈夫曼树代码：#include <stdio.h>#include <string.h>#include <time.h>#include <stdlib.h>typedef struct Node{ //定义树结构int data;struct Node *leftchild;struct Node *rightchild;}Tree;typedef struct Data{ //定义字符及其对应的频率的结构int data;//字符对应的频率是随机产生的char c;};void Initiate(Tree **root);//初始化节点函数int getMin(struct Data a[],int n);//得到a中数值（频率）最小的数void toLength(char s[],int k);//设置有k个空格的串svoid set(struct Data a[],struct Data b[]);//初始化a,且将a备份至bchar getC(int x,struct Data a[]);//得到a中频率为x对应的字符void prin(struct Data a[]);//输出初始化后的字符及对应的频率int n;void main(){//srand((unsigned)time(NULL));Tree *root=NULL,*left=NULL,*right=NULL,*p=NULL; int min,num;int k=30,j,m;struct Data a[100];struct Data b[100];int i;char s[100]={'\0'},s1[100]={'\0'};char c;set(a,b);prin(a);Initiate(&root);Initiate(&left);Initiate(&right);Initiate(&p);//设置最底层的左节点min=getMin(a,n);left->data=min;left->leftchild=NULL;left->rightchild=NULL;//设置最底层的右节点min=getMin(a,n-1);right->data=min;right->leftchild=NULL;right->rightchild=NULL;root->data=left->data+right->data;Initiate(&root->leftchild);Initiate(&root->rightchild);//将设置好的左右节点插入到root中root->leftchild=left;root->rightchild=right;for(i=0;i<n-2;i++){min=getMin(a,n-2-i);Initiate(&left);Initiate(&right);if(min<root->data)//权值小的作为左节点{left->data=min;left->leftchild=NULL;left->rightchild=NULL;p->data=min+root->data;Initiate(&p->leftchild);Initiate(&p->rightchild);p->leftchild=left;p->rightchild=root;root=p;}else{right->data=min;right->leftchild=NULL;right->rightchild=NULL;p->data=min+root->data;Initiate(&p->leftchild);Initiate(&p->rightchild);p->leftchild=root;p->rightchild=right;root=p;}Initiate(&p);}num=n-1;p=root;printf("哈夫曼树如下图:\n");while(num){if(num==n-1){for(j=0;j<k-3;j++)printf(" ");printf("%d\n",root->data);}for(j=0;j<k-4;j++)printf(" ");printf("/ \\\n");for(j=0;j<k-5;j++)printf(" ");printf("%d",root->leftchild->data);printf(" %d\n",root->rightchild->data);if(root->leftchild->leftchild!=NULL){root=root->leftchild;k=k-2;}else{root=root->rightchild;k=k+3;}num--;}num=n-1;Initiate(&root);root=p;printf("各字符对应的编码如下:\n");while(num){if(root->leftchild->leftchild==NULL){strcpy(s1,s);m=root->leftchild->data;c=getC(m,b);printf("%c 【%d】:%s\n",c,m,strcat(s1,"0"));}if(root->rightchild->leftchild==NULL){strcpy(s1,s);m=root->rightchild->data;c=getC(m,b);printf("%c 【%d】:%s\n",c,m,strcat(s1,"1"));}if(root->leftchild->leftchild!=NULL){strcat(s,"0");root=root->leftchild;}if(root->rightchild->leftchild!=NULL){strcat(s,"1");root=root->rightchild;}num--;}}int getMin(struct Data a[],int n){int i,t;for(i=1;i<n;i++){if(a[i].data<a[0].data){t=a[i].data;a[i].data=a[0].data;a[0].data=t;}}t=a[0].data;for(i=0;i<n-1;i++){a[i]=a[i+1];}return t;}void toLength(char s[],int k){int i=0;for(;i<k;i++)strcat(s," ");}void Initiate(Tree **root){*root=(Tree *)malloc(sizeof(Tree));(*root)->leftchild=NULL;(*root)->rightchild=NULL;}void set(struct Data a[],struct Data b[]) {int i;srand((unsigned)time(NULL));n=rand()%10+2;for(i=0;i<n;i++){a[i].data=rand()%100+1;a[i].c=i+97;b[i].data=a[i].data;b[i].c=a[i].c;if(i>=0&&a[i].data==a[i-1].data)i--;}}char getC(int x,struct Data b[]){int i;for(i=0;i<n;i++){if(b[i].data==x){break;}}return b[i].c;}void prin(struct Data a[]){int i;printf("字符\t出现的频率\n");for(i=0;i<n;i++){printf("%c\t %d\n",a[i].c,a[i].data);}}。

哈夫曼编码问题总结
哈夫曼编码是一种常见的数据压缩算法，但在实践中常常遇到各种问题。

以下是哈夫曼编码问题的总结：
1. 频率表不准确：哈夫曼编码的核心是根据字符出现的频率构建树结构，如果频率表不准确，树的构建就会出现问题。

因此，在使用哈夫曼编码前，需要确保频率表的准确性。

2. 编码长度不一：哈夫曼编码是一种变长编码，不同字符的编码长度不一定相同。

如果出现某个字符的编码长度过长，就会导致压缩效果变差。

为了避免这种情况，可以使用贪心算法来构建哈夫曼树，使得每个字符的编码长度尽可能短。

3. 解码效率低：在解码哈夫曼编码时，需要遍历整个哈夫曼树，查找对应的字符。

如果哈夫曼树过大，解码效率就会变低。

为了提高解码效率，可以使用哈夫曼编码的反向索引表来加速查找。

4. 压缩效果不佳：尽管哈夫曼编码可以大幅度减少数据的存储空间，但在某些情况下，压缩效果可能不如其他算法。

例如，对于随机分布的数据，哈夫曼编码的效果很差。

因此，在选择数据压缩算法时，需要根据具体情况进行选择。

总之，哈夫曼编码是一种强大的数据压缩算法，但在实践中需要注意以上问题。

只有对这些问题有充分的了解和掌握，才能更好地运用哈夫曼编码来实现数据压缩。

- 1 -。

实验四 哈夫曼编码的贪心算法设计（4学时）[实验目的]１. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法;２. 编程实现哈夫曼编译码器;３. 掌握贪心算法的一般设计方法。

实验目的和要求（1）了解前缀编码的概念，理解数据压缩的基本方法；（2）掌握最优子结构性质的证明方法；（3）掌握贪心法的设计思想并能熟练运用（4）证明哈夫曼树满足最优子结构性质；（5）设计贪心算法求解哈夫曼编码方案；（6）设计测试数据，写出程序文档。

实验内容设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。

核心源代码#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct{unsigned int weight; //用来存放各个结点的权值unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针} HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码∑=ji k k a//选择两个parent为0，且weight最小的结点s1和s2 void Select(HuffmanTree *ht,int n,int *s1,int *s2){int i,min;for(i=1; i<=n; i++){if((*ht)[i].parent==0){min=i;break;}}for(i=1; i<=n; i++){if((*ht)[i].parent==0){if((*ht)[i].weight<(*ht)[min].weight)min=i;}}*s1=min;for(i=1; i<=n; i++){if((*ht)[i].parent==0 && i!=(*s1)){min=i;break;}}for(i=1; i<=n; i++){if((*ht)[i].parent==0 && i!=(*s1)){if((*ht)[i].weight<(*ht)[min].weight)min=i;}}*s2=min;}//构造哈夫曼树ht,w存放已知的n个权值void CrtHuffmanTree(HuffmanTree *ht,int *w,int n) {int m,i,s1,s2;m=2*n-1; //总共的结点数*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(i=1; i<=n; i++) //1--n号存放叶子结点，初始化{(*ht)[i].weight=w[i];(*ht)[i].LChild=0;(*ht)[i].parent=0;(*ht)[i].RChild=0;}for(i=n+1; i<=m; i++) //非叶子结点的初始化{(*ht)[i].weight=0;(*ht)[i].LChild=0;(*ht)[i].parent=0;(*ht)[i].RChild=0;}printf("\n哈夫曼树为: \n");for(i=n+1; i<=m; i++) //创建非叶子结点，建哈夫曼树{ //在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2 Select(ht,i-1,&s1,&s2);(*ht)[s1].parent=i;(*ht)[s2].parent=i;(*ht)[i].LChild=s1;(*ht)[i].RChild=s2;(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;printf("%d (%d, %d)\n",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight);}printf("\n");}//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n){char *cd; //定义的存放编码的空间int a[100];int i,start,p,w=0;unsigned int c;hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针cd=(char *)malloc(n*sizeof(char)); //分配求当前编码的工作空间cd[n-1]='\0'; //从右向左逐位存放编码，首先存放编码结束符for(i=1; i<=n; i++) //求n个叶子结点对应的哈夫曼编码{a[i]=0;start=n-1; //起始指针位置在最右边for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //从叶子到根结点求编码{if( (*ht)[p].LChild==c){cd[--start]='1'; //左分支标1a[i]++;}else{cd[--start]='0'; //右分支标0a[i]++;}}hc[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间strcpy(hc[i],&cd[start]); //将cd复制编码到hc}free(cd);for(i=1; i<=n; i++)printf(" 权值为%d的哈夫曼编码为：%s\n",(*ht)[i].weight,hc[i]);for(i=1; i<=n; i++)w+=(*ht)[i].weight*a[i];printf(" 带权路径为：%d\n",w);}void main(){HuffmanTree HT;HuffmanCode HC;int *w,i,n,wei;printf("**哈夫曼编码**\n" );printf("请输入结点个数：" );scanf("%d",&n);w=(int *)malloc((n+1)*sizeof(int)); printf("\n输入这%d个元素的权值:\n",n); for(i=1; i<=n; i++){printf("%d: ",i);fflush(stdin);scanf("%d",&wei);w[i]=wei;}CrtHuffmanTree(&HT,w,n); CrtHuffmanCode(&HT,&HC,n);}实验结果实验体会哈夫曼编码算法：每次将集合中两个权值最小的二叉树合并成一棵新二叉树，n-1次合并后，成为最终的一棵哈夫曼树。

哈夫曼编码贪心算法时间复杂度
哈夫曼编码的贪心算法时间复杂度为O(nlogn)，其中n为待编
码的字符数量。

算法的主要步骤包括构建哈夫曼树和生成编码表两部分。

构建哈夫曼树的时间复杂度为O(nlogn)，其中n为待编码的字
符数量。

构建哈夫曼树的过程涉及到对字符频次列表进行排序，并不断合并频次最小的两个节点，直至只剩下一个节点作为根节点。

排序的时间复杂度为O(nlogn)，每次合并两个节点的时间复杂度为O(logn)。

因此，构建哈夫曼树的总时间复杂度为
O(nlogn)。

生成编码表的时间复杂度同样为O(nlogn)，其中n为待编码的字符数量。

生成编码表的过程是遍历哈夫曼树的每个节点，并记录下每个字符所对应的编码。

由于哈夫曼树的每个叶子节点代表一个字符，因此遍历哈夫曼树的时间复杂度为O(n)，并
且遍历过程的时间复杂度与树的高度相关，由于哈夫曼树是一个二叉树，因此树的高度为O(logn)。

因此，生成编码表的总
时间复杂度为O(nlogn)。

综上所述，哈夫曼编码的贪心算法的时间复杂度为O(nlogn)。

哈夫曼编码贪心算法
一、哈夫曼编码
哈夫曼编码（Huffman Coding）是一种著名的数据压缩算法，也称作霍夫曼编码，由美国信息论家杰弗里·哈夫曼在1952年提出[1]。

哈夫曼编码可以有效地将资料压缩至最小，它的原理是将资料中出现频率最高的字元编码为最短的码字，而出现频率低的字元编码为较长的码字，从而显著提高了信息的保密性和容量。

二、贪心算法
贪心算法（Greedy Algorithm）是一种计算机算法，它试图找到一种满足条件的最佳解决方案，通常每一步都是做出在当前状态下最佳的选择，而不考虑将来可能发生的结果。

哈夫曼编码贪心算法是利用贪心算法来实现哈夫曼编码的。

该算法的步骤如下：
1. 首先统计出每一个字符出现的次数，并以此建立森林。

森林
中的每一棵树都用一个节点表示，每个节点的数值为字符出现的次数。

2. 从森林中挑选出两个出现次数最少的字符，将它们作为左右
子树合成一颗新的树，新树的根节点的数值为两个孩子节点的和。

3. 将新树加入森林中，并删除左右子树对应的原节点。

4. 重复上述步骤，直到森林中只剩一颗树，这颗树就是哈夫曼树。

5. 从哈夫曼树根节点出发，逐层往下搜索，左子节点编码为“0”，右子节点编码为“1”，最终得到每个字符的哈夫曼编码。

huffman编码的基本原理
Huffman编码是一种基于贪心算法的压缩算法，其基本原理是将出现频率较高的字符用较短的编码表示，而将出现频率较低的字符用较长的编码表示，从而达到数据压缩的目的。

具体来说，Huffman编码的过程分为两步：首先统计所有字符出现的频率，并将其构建成一个树状结构；其次，根据该树状结构为每个字符生成对应的编码。

在构建树状结构时，我们可以使用最小堆或者优先队列等数据结构来实现。

具体来说，我们可以首先将所有字符出现的频率存入堆中，然后每次从堆中选取两个频率最小的字符节点，将它们合并成一个新的节点，并将其频率设为两个节点频率之和，最后再将新节点加入堆中。

这个过程将持续到堆中只剩下一个节点为止，这个节点即为哈夫曼树的根节点。

生成编码时，从根节点出发，每次遇到左孩子将编码加上0，每次遇到右孩子将编码加上1。

最终，每个字符都可以通过该树状结构得到唯一的编码。

编码的长度即为该字符在哈夫曼树中所处的深度。

Huffman编码的优点是可以根据数据本身的特点来生成最优编码，从而达到较好的压缩效果。

其缺点是需要占用额外的存储空间来存储哈夫曼树，同时编码和解码的速度较慢。

- 1 -。

算法分析与设计实验报告第次实验附录：完整代码#include <iostream>#include <string>#include<stdio.h>#include <time.h>#include <iomanip>#include <vector>#include<algorithm>using namespace std;class Huffman{public:char elementChar;//节点元素int weight;//权重char s;//哈夫曼编码Huffman* parent;//父节点Huffman* leftChild;//左孩子Huffman* rightChild;//右孩子public:Huffman();Huffman(char a, int weight);bool operator < (const Huffman &m)const { return weight < m.weight;} };Huffman::Huffman(){this->s = ' ';this->elementChar = '*';//非叶子节点this->parent = this->leftChild = this->rightChild = NULL;}Huffman::Huffman(char a, int weight):elementChar(a),weight(weight) {this->s = ' ';this->elementChar = '*';//非叶子节点this->parent = this->leftChild = this->rightChild = NULL;}//递归输出哈夫曼值void huffmanCode(Huffman & h){if(h.leftChild == NULL && h.rightChild == NULL){//如果是叶子节点，输出器哈夫曼编码string s;Huffman temp = h;while(temp.parent != NULL){s = temp.s + s;temp = *temp.parent;}cout << h.elementChar << "的哈夫曼编码是：" << s << endl; return;}//左孩子huffmanCode(*h.leftChild);//右孩子huffmanCode(*h.rightChild);}int main(){int l,p=0;double q=0.0;clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();string huffmanStr;cout << "请输入一串字符序列：" << endl;cin >> huffmanStr;//得到字符串信息int i=0,j,n,m[100],h,k=0;char cha[100];n = huffmanStr.length();cout << "字符串总共有字符" << n << "个" << endl;for(int i = 0; i < n; i++){j = 0; h = 0;while(huffmanStr[i] != huffmanStr[j])j++;if(j == i){cha[k] = huffmanStr[i];cout << "字符" << cha[k] << "出现";}//如果j !=i 则略过此次循环elsecontinue;for(j = i; j < n; j++){if(huffmanStr[i] == huffmanStr[j])h++;}cout << h << "次" << endl;m[k] = h;k++;}//哈夫曼编码Huffman huffmanTemp;vector < Huffman > huffmanQueue;//初始化队列for(int i = 0; i < k; i++){huffmanTemp.elementChar = cha[i];huffmanTemp.weight = m[i];huffmanQueue.push_back(huffmanTemp);}//得到哈夫曼树所有节点int huffmanQueue_index = 0;sort(huffmanQueue.begin(), huffmanQueue.end());while(huffmanQueue.size() < 2 * k - 1){//合成最小两个节点的父节点huffmanTemp.weight = huffmanQueue[huffmanQueue_index].weight + huffmanQueue[huffmanQueue_index + 1].weight;huffmanQueue[huffmanQueue_index].s = '0';huffmanQueue[huffmanQueue_index + 1].s = '1';huffmanTemp.elementChar = '*';//将父节点加入队列huffmanQueue.push_back(huffmanTemp);sort(huffmanQueue.begin(), huffmanQueue.end());huffmanQueue_index += 2;}//把所有节点构造成哈夫曼树int step = 0;//步长while(step + 2 < 2 * k){for(int j = step + 1; j <= huffmanQueue.size(); j++){if(huffmanQueue[j].elementChar == '*' && huffmanQueue[j].leftChild == NULL && (huffmanQueue[j].weight == huffmanQueue[step].weight + huffmanQueue[step+1].weight)){huffmanQueue[j].leftChild = &huffmanQueue[step];huffmanQueue[j].rightChild = &huffmanQueue[step+1];huffmanQueue[step].parent = huffmanQueue[step+1].parent = &huffmanQueue[j]; break;}}step += 2;}//序列最后一个元素，即哈弗曼树最顶端的节点huffmanTemp = huffmanQueue.back();huffmanCode(huffmanTemp);for(l=0;l<1000000000;l++)p=p+l;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK);return 0;}。

哈夫曼编码的贪心算法时间复杂度哈夫曼编码的贪心算法时间复杂度在信息技术领域中，哈夫曼编码是一种被广泛应用的数据压缩技术，它利用了贪心算法的思想来设计。

贪心算法是一种在每一步都选择当前状态下最优解的方法，从而希望通过一系列局部最优解达到全局最优解。

在哈夫曼编码中，这个想法被巧妙地运用，从而有效地实现了数据的高效压缩和解压缩。

哈夫曼编码是由大名鼎鼎的大卫·哈夫曼（David A. Huffman）在1952年提出的，它通过将频率最高的字符赋予最短的编码，最低的字符赋予最长的编码，从而实现了对数据的高效压缩。

这种编码技术在通信领域、存储领域和计算机科学领域都有着广泛的应用，是一种非常重要的数据处理技术。

在哈夫曼编码的实现过程中，贪心算法的时间复杂度是非常重要的。

时间复杂度是用来衡量算法所需时间的数量级，通常使用大O记号（O(n)）来表示。

对于哈夫曼编码的贪心算法来说，其时间复杂度主要取决于以下几个步骤：1. 需要对数据进行统计，以获取每个字符出现的频率。

这个步骤的时间复杂度是O(n)，其中n表示字符的数量。

在实际应用中，这个步骤通常由哈希表或统计排序来实现，因此时间复杂度可以控制在O(n)的数量级。

2. 接下来，需要构建哈夫曼树。

哈夫曼树是一种特殊的二叉树，它的构建过程需要将频率最低的两个节点合并成一个新的节点，然后再对新节点进行排序。

这个过程会持续n-1次，直到所有节点都被合并到一棵树中。

构建哈夫曼树的时间复杂度是O(nlogn)，其中n表示字符的数量。

3. 根据哈夫曼树生成每个字符的编码。

这个过程涉及到对哈夫曼树进行遍历，并记录下每个字符对应的编码。

由于哈夫曼树的特性，每个字符的编码可以通过从根节点到叶子节点的路径来得到。

这个步骤的时间复杂度是O(n)，因为对于每个字符都需要进行一次遍历。

哈夫曼编码的贪心算法时间复杂度主要由构建哈夫曼树的步骤决定，为O(nlogn)。

这意味着在实际应用中，哈夫曼编码的运行时间随着字符数量的增加而增加，并且增长速度为nlogn的数量级。

1.问题描述哈夫曼编码（贪心策略）——要求给出算法思想、编码程序和译码程序，对样本数据“哈夫曼编码实验数据.dat”，要求提交符号的具体编码以及编码后的文件。

2.求解问题的贪心算法描述压缩数据由以下步骤组成：a）检查字符在数据中的出现频率。

b）构建哈夫曼树。

c）创建哈夫曼编码表。

d）生成压缩后结果，由一个文件头和压缩后的数据组成。

3.算法实现的关键技巧1.最小堆两种基本操作：插入新元素，抽取最小元素。

（1）插入新元素：把该元素放在二叉树的末端，然后从该新元素开始，向根节点方向进行交换，直到它到达最终位置。

（2）抽取最小元素：把根节点取走。

然后把二叉树的末端节点放到根节点上，然而把该节点向子结点反复交换，直到它到达最终位置。

2. 构建哈夫曼树：a）把所有出现的字符作为一个节点（单节点树），把这些树组装成最小堆；b）从该优先级队列中连续抽取两个频率最小的树分别作为左子树，右子树，将他们合并成一棵树（频率=两棵树频率之和），然后把这棵树插回队列中。

c）重复步骤b，每次合并都将使优先级队列的尺寸减小1，直到最后队列中只剩一棵树为止，就是我们需要的哈夫曼树。

3.压缩数据: 遍历输入的文本，对每个字符，根据编码表依次把当前字符的编码写入到编码结果中去。

File Header（文件头）：unsigned int size; 被编码的文本长度（字符数）；unsigned char freqs[ NUM_CHARS ]; 字符频率表compressed; (Bits: 压缩后的数据）；4.贪心选择性质&最优子结构性质证明：即证明最优前缀码问题具有弹性选择性质和最优子结构性质.(1)贪心选择性质设C是编码字符集,C中字符c的频率为f(c)。

又设x,y是C中具有最小频率的两个字符，则存在C的最优前缀码使x,y具有相同码长且仅最后一位编码不同。

证明：设二叉树T表示C的任意一个最优前缀码。

对C左适当修改得到T“,使得在新树中，x和y是最深叶子且为兄弟。

算法与分析1.哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。

给出文件中各个字符出现的频率，求各个字符的哈夫曼编码方案。

2.给定带权有向图G =(V,E)，其中每条边的权是非负实数。

另外，还给定V中的一个顶点，称为源。

现在要计算从源到所有其他各顶点的最短路长度。

这里路的长度是指路上各边权之和。

3.设G =(V,E)是无向连通带权图，即一个网络。

E中每条边(v,w)的权为c[v][w]。

如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。

生成树上各边权的总和称为该生成树的耗费。

在G的所有生成树中，耗费最小的生成树称为G的最小生成树。

求G的最小生成树。

求解问题的算法原理：1.最优装载哈夫曼编码1.1前缀码对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀，这种编码称为前缀码。

编码的前缀性质可以使译码方法非常简单。

表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。

平均码长定义为：B(T)=∑∈CcTcdcf)()(f(c):c的码长，dt(c):c的深度使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。

1.2构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。

哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。

算法以|C|个叶结点开始，执行|C|-1次的“合并”运算后产生最终所要求的树T。

编码字符集中每一字符c的频率是f(c)。

以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。

一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。

经过n-1次的合并后，优先队列中只剩下一棵树，即所要求的树T。

可用最小堆实现优先队列Q。

2.单源最短路径Dijkstra算法是解单源最短路径问题的贪心算法。

其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。