page2
Huffman Coding
procedure Huffman(C: symbols ai with freq. wi,i = 1,...,n)
F := forest of n rooted trees, each contains a single
vertex ai and assigned weight wi.
while F is not a tree
Take two rooted trees, T and T', with the least
weights and w(T)  w(T').
Replace them with a tree having a new root that
has T as its left subtree and T' as its right subtree.
Label the edge to T with 0, and the edge to T' with 1.
Assign w(T)+w(T') as the weight of the new tree.
Output: Huffman code for ai: the concatenation of labels of
the edges in the unique path from the root to the vertex vi.
Example: Use Huffman coding to encode the following symbols with the frequencies:
A: 0.10 110
B: 0.25 10
C: 0.05 0111
D: 0.15 010
E: 0.30 00
F: 0.07 0110
G: 0.08 111
the average number of
bits required to encode a symbol is
3 * 0.10 + 2 * 0.25 + 4 * 0.05 + 3 * 0.15 +
2 * 0.3 + 4 * 0.07 + 3 * 0.08 = 2.57
C
F
D
E
0
1
0
1
0
1
A
G
B
0
1
0
1
0
1
Tree traversals:
preorder traversal :
visit parent r, then
traverse child T1 in preorder,
…
traverse child Tn in preorder.
inorder traversal :
traverse child T1 in inorder,
visit parent r,
traverse child T2 in inorder,
…
traverse Tn in inorder.
postorder traversal :
traverse child T1 in postorder,
…
traverse child Tn in postorder,
visit parent r.
An inorder traversal of T (fully parenthesised) produces the expression in infix notation:
The preorder traversal of T produces the expression in prefix notation:
The postorder traversal of T produces the expression in postfix notation / Polish notation:
Depth-First Search:
procedure DFS(G: connected graph with
vertices v1, v2,…, vn)
T := tree consisting only of vertex v1
visit(v1)
procedure visit(v: vertex of G)
for each vertex w adjacent to v and
not yet in T,
add vertex w and edge {v,w} to T
visit(w)
Breadth-First Search:
procedure BFS(G: connected graph with
vertices v1, v2,…, vn)
T := tree consisting only of vertex v1
L := empty list
put v1 in the list L of unprocessed vertices
while L is not empty
remove the first vertex, v, from L
for each neighbor w of v
if w is not in L and not in T then
add w to the end of the list L
add w and edge {v,w} to T
Prim's algorithm:
procedure Prim(G: weighted connected
undirected graph with n vertices)
T := a minimum weight edge
for i := 1 to n-2
e := an edge of min. weight incident to a vertex in T
and not forming a simple circuit in T if added to T
T := T with added edge e
return T
We will assume that the edges are ordered when we need to choose between two or more edges with the same weights.
Kruskal's algorithm:
procedure Kruskal(G: weighted connected
undirected graph with n vertices)
T:= empty graph
for i := 1 to n-1
e:= any edge in G with smallest weight that
does not form a simple circuit when added to T
T := T with added e
return T