最大流 — Edmond Karp算法

Edmond Karp算法的大概思想:

反复寻找源点s到汇点t之间的增广路径,若有,找出增广路径上每一段[容量-流量]的最小值delta,若无,则结束。

在寻找增广路径时,可以用BFS来找,并且更新残留网络的值(涉及到反向边)。

而找到delta后,则使最大流值加上delta,更新为当前的最大流值。

(粗体表明需要掌握的概念)

继续阅读最大流 — Edmond Karp算法

《算法导论》学习总结 — XX.第24章 单源最短路径

建议先看看前言:http://www.wutianqi.com/?p=2298

更多单源最短路径算法见我的算法专题:http://www.wutianqi.com/sfzt.html

这里我补充一些里面未写到的。

继续阅读《算法导论》学习总结 — XX.第24章 单源最短路径

《算法导论》学习总结 — XX.第23章 最小生成树

建议先看看前言:http://www.wutianqi.com/?p=2298

以前写过一篇最小生成树的文章,见:http://www.wutianqi.com/?p=1284

最小生成树(Minimum Spanning Tree),全称“最小权值生成树”

有两种具体的实现算法

1.Kruskal算法

2.Prim算法

两者都用到了贪心算法。

继续阅读《算法导论》学习总结 — XX.第23章 最小生成树

Huffman树简单总结+代码(C/C++)

Huffman树,中文霍夫曼树或哈夫曼树,又称最优二叉树,是一种带权路径长最短的树。

  • Huffman树的构建思想:

1.从原始元素集合T中拿出两个频度最小的元素组成一个二叉树,二叉树的根为这两个节点频度的和。

2.然后从集合T中删除这两个元素,把根元素加入到T集合中,如此反复直集合T为空。

  • 构建此过程的数据结构:

1.优先级队列

2.顺序存储结构

3.二叉链表(本文所用)

  • 逐步分析:

1.Huffman树的结构(二叉链表表示):

1
2
3
4
5
6
typedef struct{
    unsigned int weight;
    unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;   //动态分配数组存储哈夫曼树
 
typedef char* HuffmanCode;   //动态分配数组存储哈夫曼编码表

2.SelectMin函数用于筛选最小的两个数,其中s1用于保存最小的,置于左孩子结点,s2保存第二小的,置于右孩子结点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//选出weight最小的两个结点,s1保存最小的,s2保存第二小的
void SelectMin(HuffmanTree HT, int nNode)
{
    int i, j;
    for(i = 1; i <= nNode; i++)
        if(!HT[i].parent)
        {
            s1 = i;
            break;
        }
    for(j = i+1; j <= nNode; j++)
        if(!HT[j].parent)
        {
            s2 = j;
            break;
        }
 
    for(i = 1; i <= nNode; i++)
        if((HT[i].weight < HT[s1].weight) && (!HT[i].parent) && (s2 != i))
            s1 = i;
    for(j = 1; j <= nNode; j++)
        if((HT[j].weight < HT[s2].weight) && (!HT[j].parent) && (s1 != j))
            s2 = j;
    // 以上只筛选出最小的两个,这里保证s1的weight比s2的小
    if(HT[s1].weight > HT[s2].weight)
    {
        int tmp = s1;
        s1 = s2;
        s2 = tmp;
    }
}

3.最后的HaffmanCoding:

可以分为三部分,分别是Huffman树的初始化,创建,以及编码
代码里已经详细注释了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// w[]存放nNode个字符的权值(均大于0),构造哈夫曼树HT,
// 并求出nNode个字符的哈夫曼编码HC
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int nNode)
{
    int i, j;
    char *hfcode;
    int p;
    int cdlen;
    if(nNode < 1)
        return;
    m = 2*nNode-1;   //哈夫曼树的结点数
 
    /////////////////////////////以下是求Huffman树的初始化/////////////////////////////
    HT = (HTNode*) malloc ((m+1) *sizeof(HTNode));  //0号单元未用
    for(i = 1; i <= nNode; i++)    //初始化
    {
        HT[i].weight = w[i-1];
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    for(i = nNode+1; i <= m; i++)
    {
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
 
    puts("\n哈夫曼树的构造过程如下所示: ");
    printf("HT初态:\n 结点 weight parent lchild rchild");
    for(i = 1; i <= nNode; i++)
        printf("\n%4d%8d%8d%8d%8d", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
 
    printf("按任意键,继续...");
    getchar();
 
    /////////////////////////////以下是求Huffman树的构建/////////////////////////////
    for(i = nNode+1; i <= m; i++)
    {
        // 建立哈夫曼树
        // 在HT[1..i-1]中选择parent为0且weight最小的两个节点
        // 其序号分别是s1和s2
        SelectMin(HT, i-1);
        HT[s1].parent = i;
        HT[s2].parent = i;
        cout << "S1 && S2: " << HT[s1].weight << " " << HT[s2].weight << endl;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
        printf("\nselect: s1 = %d s2 = %d\n", s1, s2);
        printf("结点 weight parent lchild rchild");
        for(j = 1; j <= i; j++)
            printf("\n%4d%8d%8d%8d%8d", j, HT[j].weight, HT[j].parent, HT[j].lchild, HT[j].rchild);
        printf("按任意键,继续...");
        getchar();
    }
 
 
    /////////////////////////////以下是求Huffman树的编码/////////////////////////////
    // 可以看看算法导论上对于DFS求路径的方法,分三色:白,灰,黑,这里weight=0,1,2和那里思想是类似的
    // 可以拿7,5,2,4这组数据来模拟下面的过程,以求更简单理解
    // 从根出发
    //递归遍历哈夫曼树,求哈夫曼编码
    hfcode = (char *) malloc (nNode * sizeof(char));   //分配求编码的工作空间
    p = m;
    cdlen = 0;
    for(i = 1; i <= m; i++)
        HT[i].weight = 0;   //遍历哈夫曼树时用作结点状态的标志
 
    while(p)        //退出条件:p = 结点m的parent,即为0
    {
        if(HT[p].weight == 0)   //向左
        {
            HT[p].weight = 1;
            if(HT[p].lchild != 0)
            {
                p = HT[p].lchild;
                hfcode[cdlen++] = '0';
            }
            else if(HT[p].rchild == 0)
            {
                HC[p] = (char *) malloc ((cdlen+1) * sizeof(char));
                hfcode[cdlen] = '\0';   //保证后面的不会被复制
                strcpy(HC[p], hfcode);   //复制编码
            }
        }
        else if(HT[p].weight == 1)   //向右
        {
            HT[p].weight = 2;
            if(HT[p].rchild != 0)
            {
                p = HT[p].rchild;
                hfcode[cdlen++] = '1';
            }
        }
        else
        {
            // HT[p].weight == 2 退回到父结点,编码长度减一
            HT[p].weight = 0;
            p = HT[p].parent;
            --cdlen;
        }
    }
}
  • 完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/*
 * Tanky Woo
 * Blog: www.WuTianQi.com
 * Description: Huffman Tree
 * Date: 2011.12.3
*/
#include <iostream>
using namespace std;
 
int m, s1, s2; // m是总结点个数,s1,s2用于筛选出最小和第二小的两个数
 
typedef struct{
    unsigned int weight;
    unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;   //动态分配数组存储哈夫曼树
 
typedef char* HuffmanCode;   //动态分配数组存储哈夫曼编码表
 
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int nNode);
 
int main()
{
    HuffmanTree HT;   // 哈夫曼树
    HuffmanCode *HC;  // 保存哈夫曼编码
    int *w, nNode, i; // w记录权值
    puts("输入结点数: ");
    scanf("%d", &nNode);
    HC = (HuffmanCode *) malloc (nNode* sizeof(HuffmanCode));
    w = (int *) malloc (nNode * sizeof(int));
    printf("输入 %d 个结点的权值\n", nNode);
    for(i = 0; i < nNode; i++)
        scanf("%d", &w[i]);
    HuffmanCoding(HT, HC, w, nNode);
    puts("\n各结点的哈夫曼编码:");   
    for(i = 1; i <= nNode; i++)
        printf("%2d(%4d):%s\n", i, w[i-1], HC[i]);
    getchar();
}
 
//选出weight最小的两个结点,s1保存最小的,s2保存第二小的
void SelectMin(HuffmanTree HT, int nNode)
{
    int i, j;
    for(i = 1; i <= nNode; i++)
        if(!HT[i].parent)
        {
            s1 = i;
            break;
        }
    for(j = i+1; j <= nNode; j++)
        if(!HT[j].parent)
        {
            s2 = j;
            break;
        }
 
    for(i = 1; i <= nNode; i++)
        if((HT[i].weight < HT[s1].weight) && (!HT[i].parent) && (s2 != i))
            s1 = i;
    for(j = 1; j <= nNode; j++)
        if((HT[j].weight < HT[s2].weight) && (!HT[j].parent) && (s1 != j))
            s2 = j;
    // 以上只筛选出最小的两个,这里保证s1的weight比s2的小
    if(HT[s1].weight > HT[s2].weight)
    {
        int tmp = s1;
        s1 = s2;
        s2 = tmp;
    }
}
 
// w[]存放nNode个字符的权值(均大于0),构造哈夫曼树HT,
// 并求出nNode个字符的哈夫曼编码HC
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int nNode)
{
    int i, j;
    char *hfcode;
    int p;
    int cdlen;
    if(nNode < 1)
        return;
    m = 2*nNode-1;   //哈夫曼树的结点数
 
    /////////////////////////////以下是求Huffman树的初始化/////////////////////////////
    HT = (HTNode*) malloc ((m+1) *sizeof(HTNode));  //0号单元未用
    for(i = 1; i <= nNode; i++)    //初始化
    {
        HT[i].weight = w[i-1];
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    for(i = nNode+1; i <= m; i++)
    {
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
 
    puts("\n哈夫曼树的构造过程如下所示: ");
    printf("HT初态:\n 结点 weight parent lchild rchild");
    for(i = 1; i <= nNode; i++)
        printf("\n%4d%8d%8d%8d%8d", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
 
    printf("按任意键,继续...");
    getchar();
 
    /////////////////////////////以下是求Huffman树的构建/////////////////////////////
    for(i = nNode+1; i <= m; i++)
    {
        // 建立哈夫曼树
        // 在HT[1..i-1]中选择parent为0且weight最小的两个节点
        // 其序号分别是s1和s2
        SelectMin(HT, i-1);
        HT[s1].parent = i;
        HT[s2].parent = i;
        cout << "S1 && S2: " << HT[s1].weight << " " << HT[s2].weight << endl;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
        printf("\nselect: s1 = %d s2 = %d\n", s1, s2);
        printf("结点 weight parent lchild rchild");
        for(j = 1; j <= i; j++)
            printf("\n%4d%8d%8d%8d%8d", j, HT[j].weight, HT[j].parent, HT[j].lchild, HT[j].rchild);
        printf("按任意键,继续...");
        getchar();
    }
 
 
    /////////////////////////////以下是求Huffman树的编码/////////////////////////////
    // 可以看看算法导论上对于DFS求路径的方法,分三色:白,灰,黑,这里weight=0,1,2和那里思想是类似的
    // 可以拿7,5,2,4这组数据来模拟下面的过程,以求更简单理解
    // 从根出发
    //递归遍历哈夫曼树,求哈夫曼编码
    hfcode = (char *) malloc (nNode * sizeof(char));   //分配求编码的工作空间
    p = m;
    cdlen = 0;
    for(i = 1; i <= m; i++)
        HT[i].weight = 0;   //遍历哈夫曼树时用作结点状态的标志
 
    while(p)        //退出条件:p = 结点m的parent,即为0
    {
        if(HT[p].weight == 0)   //向左
        {
            HT[p].weight = 1;
            if(HT[p].lchild != 0)
            {
                p = HT[p].lchild;
                hfcode[cdlen++] = '0';
            }
            else if(HT[p].rchild == 0)
            {
                HC[p] = (char *) malloc ((cdlen+1) * sizeof(char));
                hfcode[cdlen] = '\0';   //保证后面的不会被复制
                strcpy(HC[p], hfcode);   //复制编码
            }
        }
        else if(HT[p].weight == 1)   //向右
        {
            HT[p].weight = 2;
            if(HT[p].rchild != 0)
            {
                p = HT[p].rchild;
                hfcode[cdlen++] = '1';
            }
        }
        else
        {
            // HT[p].weight == 2 退回到父结点,编码长度减一
            HT[p].weight = 0;
            p = HT[p].parent;
            --cdlen;
        }
    }
}

欢迎大家一起探讨。

  • 参考资料:

严蔚敏《数据结构》

最后给出一个题目:
http://acm.hdu.edu.cn/showproblem.php?pid=1053
HuffmanTree的题目,不过没用到求具体编码,所以相对要简单多了。
结题报告:

HDU/HDOJ 1053 Entropy (Huffman树)


http://www.cnblogs.com/Open_Source/archive/2010/07/10/1904936.html(STL优先级队列做法)