Succ(x) for each vertex x in the graph
G. For example, the successors of vertex 1 are those is the set
Succ(1) = {2,3}, meaning there are directed edges from
vertex 1 to vertices 2 and 3. Describe how to compute lists of
the predecessor vertices, Pred(x) for each x in
the graph G, starting with an adjacency matrix, T[i,j]
for G.
| Vertex Number | Adjacency List |
| 1 | 2, 3 |
| 2 | 3, 4, 5 |
| 3 | 4 |
| 4 | |
| 5 | 1 |
To compute the list of predecessors, Pred(x), for a vertex x starting with an adjacency matrix T for a graph G, you can scan column x of T and make a list of the vertices y for which T[y,x] = true. For example, letting L be an initially empty list, you could use the following program strategy:
// initialize L to be the empty list
for (y = 0; y < MaxVertexNumber; ++y) {
if (T[y][x] == true) {
L.insert(y); // insert new member y on list L
}
}
| Character | A | B | C | D | E | F | G |
| Frequency | 7 | 3 | 8 | 10 | 1 | 2 | 6 |
Recall that Huffman's algorithm is defined as follows: We maintain a forest of trees. The weight of a tree is equal to the sum of the frequencies of its leaves. We assume C is the number of characters in the tree. So, C-1 times, select the two trees, T1 and T2, of smallest weight, breaking ties arbitrarily, and form a new tree with subtrees T1 and T2. At the beginning of the algorithm, there are C single-node trees--one for each character. At the end of the algorithm there is one tree, and this is the optimal Huffman coding tree.
Here is a trace through the building of the optimal Huffman coding tree (the frequencies of the trees appear above them):
7 3 8 10 1 2 6
- - - -- - - -
A B C D E F G
--------------------------------
7 3 8 10 6 3
- - - -- - -
A B C D G T1
/ \
E F
--------------------------------
7 8 10 6 6
- - -- - -
A C D G T2
/ \
T1 B
/ \
E F
--------------------------------
7 8 10 12
- - -- --
A C D T3
/ \
T2 G
/ \
T1 B
/ \
E F
--------------------------------
10 15 12
-- -- --
D T4 T3
/ \ / \
A C T2 G
/ \
T1 B
/ \
E F
--------------------------------
15 22
-- --
T4 T5
/ \ / \
A C T3 D
/ \
T2 G
/ \
T1 B
/ \
E F
--------------------------------
The optimal Huffman coding tree:
37
--
T6
/ \
T5 T4
/ \ / \
T3 D A C
/ \
T2 G
/ \
T1 B
/ \
E F
| City | Denver | Salt Lake | Albuquerque | Oklahoma City | Cheyenne | Omaha |
| Salt Lake | 512 | |||||
| Albuquerque | 422 | 611 | ||||
| Oklahoma City | 615 | 1108 | 525 | |||
| Cheyenne | 102 | 462 | 522 | 706 | ||
| Omaha | 540 | 955 | 895 | 454 | 493 | |
| Dodge City | 301 | 682 | 425 | 212 | 355 | 336 |
The trick is to use Kruskal's Algorithm. Recall that Kruskal`s algorithm is a greedy strategy that continually selects the edges in order of smallest weight and accepts an edge if it does not cause a cycle. Formally, Kruskal's algorithm maintains a forest--a collection of trees. Initially, there are |V| single-node trees. Adding an edge merges two trees into one. When the algorithm terminates, there is only one tree, and this is the minimum spanning tree.
Here is the pseudocode for Kruskal's algorithm given in the Weiss book:
public void kruskal()
{
int edgesAccepted;
DisjSet s;
PriorityQueue h;
Vertex u, v;
SetType uset, vset;
Edge e;
h = readGraphIntoHeapArray();
h.buildHeap();
s = new DisjSet( NUM_VERTICES );
edgesAccepted = 0;
while( edgesAccepted < NUM_VERTICES - 1 )
{
e = h.deleteMin(); // Edge e = (u,v)
uset = s.find( u );
vset = s.find( v );
if ( uset != vset )
{
// Accept the edge
edgesAccepted++;
s.union( uset, vset );
}
}
}
You can think of Figure 3 as containing the adjacency matrix information for a weighted graph of cities. The pairs of cities (edges) accepted are:
Here is what the graph might look like (by the way, this graph is not geographically correct nor is it drawn to scale):
102 422
Cheyenne--------------Denver--------------Albuquerque
| |
| |
| 462 | 301
| |
| | 212
Salt Lake Dodge City-------------Oklahoma City
|
|
| 336
|
|
Omaha
Use an array count such that for any vertex u,
count[u] is the number of distinct paths from s to
u known so far. When a vertex v is marked as known, its
adjacency list is traversed. Let w be a vertex on the adjacency
list.
If dv + cv,w
= dw, then increment count[w]
by count[v] because all shortest paths from s to
v with last edge (v,w) give a shortest path to
w.
If dv + cv,w
< dw, then pw
and dw get updated. All previously known
shortest paths to w are now invalid, but all shortest paths to
v now lead to shortest paths for w, so set
count[w] to equal count[v]. Note: Zero-cost edges mess
up this algorithm.
Use an array numEdges such that for any vertex u,
numEdges[u] is the shortest number of edges on a path of distance
du from s to u known so far.
Thus numEdges is used as a tiebreaker when selecting the vertex
to mark. As before, v is the vertex marked known, and
w is adjacent to v.
If dv + cv,w
= dw, then change pw
to v and numEdges[w] to numEdges[v] + 1 if
numEdges[v] + 1 < numEdges[w].
If dv + cv,w
< dw, then update
pw
and dw, and set numEdges[w] to
numEdges[v] + 1.