# 一些算法整理

## 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
Else
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.


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.

## Docutils System Messages

System Message: ERROR/3 (<string>, line 54); backlink

Undefined substitution referenced: "V".