Kruskal's mininum spanning tree algorithm
最小生成树, 无向图,,选边的方法, 里面如何判断是否构成环比较麻烦
Input: A weighted, connected and undirected graph G = (V, E).
Output: A minimum spanning tree for G.
T := \varnothing
While T contains less than n - 1 edges do
Begin
Choose an edge(v,w) from E of the smallest weight
Delete (v,w) from E
If (the adding of (v,w) to T does not create a cycle in T) then
Add (v,w) to T
Else
Discard (v,w)
End
The basic Prim's algorithm to find a minimum spanning tree
选点.
Input: A weighted, connected and undirected graph G = (V, E). Output: A minimum spanning tree for G.
Step 1: Let x be any vertex in V. Let X = {x} and Y = V - {x}. Step 2: Select an edge (u,v) from E such that u in X, v in Y and (u,v) has the smallest weight among edges between X and Y. Step 3: Connect u to v. Let X = X U {v} and Y = Y - {v}. Step 4: If Y is empty, terminate and the resulting tree is a minimum spanning tree. Otherwise, Go to Step 2.
详细点的
Step 1: Let X = {x} and Y = V - {x} where x is any vertex in V. Step 2: Set C_1(y_j) = x and C_2(y_j) = infty for every vertex y_j in V. Step 3: For every vertex y_j in V, examine whether y_j is in Y and edge(x, y_j) exists. If y_j is in Y, edge(x,y_j) exists and w(x, y_j) = b < C_2(y_j), set C_1(y_j) = x and set C_2(y_j) = b; otherwise, do nothing. Step 4: Let y be a vertex in Y such that C_2(y) is minimum. Let z = C_1(y)(z must be in X). Connect y with edge (y, z) to z in the partially constructed tree T. Let X = X + {y} and Y = Y - {y}. Set C_2(y) = infty . Step 5: If Y is empty, terminate and the resulting tree T is a minimun spanning tree; otherwise, set x = y and go to Step 3.
Dijkstra's single source shortest paths
Input: A directed graph G = (V, E) and a source vertex v_0. For each edge (u, v) in E, there is a non-negative number c(u, v) associated with it. |V| = n + 1. Output: For each v in V. the length of a shortest path from v_0 to v.
S := { v_0 }
For i:= i to n do
Begin
if (v_0, v_i) \in E then
L(v_i) := c(v_0, v_i)
else:
L(v_i) := \infty
End
For i := 1 to n do
Begin
Choose u from V - S such that L(u) is the smallest
S := S \cup { u } /* Put u into S */
For all w in V - S do
L(w) := min(L(w), L(u) + c(u,w))
End
O(n^2)
Linear merge algorithm
Input: Two sorted lists, L_1 = (a_1, a_2, ..., a_{n_1}) and L_2 = (b_1, b_2, ..., b_{n_2}). Output: A sorted list consisting of elements in L_1 and L_2;
Begin
i := 1
j := 1
do
compare a_i and b_j
if a_i > b_j then output b_j and j := j+1
else output a_i and i := i+1
while ( i \leq n_1 and j \leq n_2)
if i > n_1 then output b_j, b_j+1, ..., b_{n_2},
else output a_i, a_i+1, ..., a_{n_1}.
End.
多路归并的话, 可以看成是一棵树, 归并时统计元素比较次数, 越少越好, 那么如果看成是一颗二叉树, 树的深度应该越少越好. 每个数组比较次数为d_i*n_i, d_i为数组i的在二叉树中的深度, n_i为数组元素个数.
A greedy algorithm to generate an optimal 2-way merge tree Input: m sorted lists, L_i, i=1,2, ..., m, each L_i consisting of n_i elements. Output: An optimal 2-vay merge tree.
Step 1: Generate m trees, where each tree has exactly one node (external node) with weight n_i. Step 2: Choose two trees T_1 and T_2 with minimal weights. Step 3: Create a new tree T whose root has T_1 and T_2 as its subtrees and weight is equal to the sum of weights of T_1 and T_2. Step 4: Replace T_1 and T_2 by T. Step 5: If there is only one tree left, stop and return; otherwise, go to Step 2.
这个过程: 依次选择最小的两棵树归并, 新的树替代这两棵, 重复找. 和构建huffman树(这树加上0, 1编码就可以得到对应的编码了)类似. 顺便回忆一下huffman编码, 使用频率最为权值, 最频繁的应该位于树根部, 对应的编码长度应该较小, 而频率低的则靠树叶子节点, 对应的编码长度相对较长.