转载自ICS161,学英语,自娱自乐

Traversal of graphs and digraphs

To traverse(遍历) means to visit the vertices in some systematic order. You should be familiar with various traversal methods for trees:

preorder: visit each node before its children.
postorder: visit each node after its children.
inorder (for binary trees only): visit left subtree, node, right subtree.

We also saw another kind of traversal, topological ordering(拓扑排序), when I talked about shortest paths.

Today, we'll see two other traversals: breadth first search (BFS) and depth first search (DFS). Both of these construct spanning trees with certain properties useful in other graph algorithms. We'll start by describing them in undirected graphs, but they are both also very useful for directed graphs.

- 阅读剩余部分 -

概念

哈夫曼树是带权路径长度 WPL（Weighted Path Length）最小的二叉树，也称为最优二叉树。

如下图：

它们的带权路径长度分别为：
图a： WPL = 5*2 + 7*2 + 2*2 + 13*2 = 54
图b： WPL = 5*3 + 2*3 + 7*2 + 13*1 = 48
可见，图b的带权路径长度较小，我们可以证明图b就是哈夫曼树(也称为最优二叉树)

- 阅读剩余部分 -