假期连载之十五
（树、图补完篇）
本篇的主要目的是对树和图部分内容中的代码进行分析，涉及构造哈夫曼树、图的几种主流应用算法等问题。本篇结束后假期系列的基本数据结构部分就暂告一段落了。
构建哈夫曼树
现在讨论构建哈夫曼树的算法实现问题。在前文已经对构造哈夫曼树的算法思路有了一定的介绍，易知哈夫曼树中没有度为1的结点，因而一棵有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。其结点结构分别是权值域、双亲序号、左子女序号、右子女序号。各结点存储在一维数组中，0号单元不用，从1号位置开始使用。
对于有n个叶子结点的哈夫曼树，结点总数为2n-1个，为实现方便，将叶子结点集中存储在前面部分1-n个位置，而后面的n-1个位置中存储其余非叶子结点。
我们给出静态三叉链表实现的哈夫曼树类型C语言描述：
#define N 20
#define M 2*N-1
typedef struct
{
int weight;
int parent;
int LChild;
int RChild;
}HTNode,HuffmanTree[M+1];
使用上述结构实现创建哈夫曼树算法：
void CrtHuffmanTree(HuffmanTree ht,int w[],int n)
{
for(i=1;i<=n;i++)
{
ht[i]={w[i],0,0,0} //初始化1—n单元的叶结点
}
m=2*n-1; //统计结点总数
for(i=n+1;i<=m;i++) //从n+1至m个结点为非叶结点
{
select(ht,i-1,&s1,&s2); //从ht中选择两个parent为0且weight最小的结点，将其序号分别赋值给s1、s2返回
ht[i].weight=ht[s1].weight+ht[s2].weight; //计算每次结合后根结点的权值
ht[s1].parent=i; //将s1、s2的父结点指定为第i个结点
ht[s2].parent=i;
ht[i].LChild=s1; //对第i个结点的左右子女结点赋值
ht[i].RChild=s2;
}
}
计算哈夫曼编码
我们知道，构建哈夫曼树的最终目的是求解哈夫曼编码，从而方便信息传输和数据压缩。因此基于哈夫曼树的哈夫曼编码计算算法就显得尤为重要了。
void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n)
{
char *cd;
cd=(char*)malloc((n+1)*sizeof(char)); //初始化空间
cd[n-1]=”\0”; //首先存放结束符
for(int i=1;i<=n;i++)
{
start=n-1; //编码起始位置
c=i;
p=ht[i].parent; //从叶结点开始倒推
while(p!=0)
{
–start; //倒推一层，判断左0右1，再推一层，直到根结点
if(ht[p].LChild==c)
{
cd[start]=’0’;
}
else
{
cd[start]=’1’;
}
c=p;
p=ht[p].parent;
}
hc[i]=(char*)malloc((n-start)*sizeof(char)); //建立哈夫曼编码存放空间
strcpy(hc[i],&cd[start]);
}
free(cd);
}
深度优先的简单路径算法
在图这一部分中，简单路径是指任意两结点路径中不含相同结点的一条。为求解图的简单路径，需要先对图中所有结点进行统一标识，每访问一个结点，则更改该结点标识符，从而达到求简单路径的目的。
算法外围的核心是给所有结点统一赋值，并且建立对应于结点且独立的带值空间。下面给出用深度优先搜索寻找从u到v的简单路径算法C语言描述。
void DFS_path(Graph *G,int u,int v)
{
int j;
for(j=firstadj(G,u);j>=0;j=nextadj(G,u,j))
{
if(pre[j]==-1) //默认结点标识为-1，一旦使用过即将标识符置为u
{
pre[j]=u;
if(j==v)
{
print_path(pre,v);
}
else
{
DFS_path(G,j,v);
}
}
}
}
生成树
生成树涉及到很多实际应用，例如搭桥问题…但利用MST性质求MST（Minimum Spanning Tree）还分别有Prim和kruskal两种角度不同的算法。
Prim算法通常被称为“加点法”，这是因为算法是在一个初始化为空的结点空间中，判断能令(u,v)最短的u对应的v结点，然后加入到空的结点空间中，反复执行直到该结点空间与图的结点空间相等。
Kruskal算法是根据权值最小的边，同时必须确保两个顶点不在同一个结点集合内，故有时Kruskal算法也被称为“加边法”。事实上以上两种算法除却初始化的部分，真正涉及到原理的代码段就已经非常简单了。
总结
对于拓扑排序、关键路径、最短路径等问题，读者应重点参照“图的应用”这一节连载，其原理已经比较详细，但由于经典算法时间复杂度高，已经有越来越多的专家学者对此提出了许多改进方案，并给出了许多算法解决方案，因此在此基础上参照相关科技文献，才能确保算法的实用性。