算法导论中的伪代码

基于《算法导论(第三版)》,殷剑平等译，机械工业出版社，2013年1月第一版。 代码块用Cpp代码块；空格两次代表层次结构；未使用斜体标注变量或性质。 Pxx(yy) 表示 PDF 文件xx页，原书页码yy页；有关系：xx = yy + 15。故之后简化，仅标注PDF页数。

排序算法

（排序算法表示从小往大排序。）

插入排序(Insertion Sort)

排序算法主要涉及本书的第二部分。 P25(10)

INSERTION_SORT(A) for j = 2 to A.length key = A[j] i = j - 1 while i > 0 and A[i] > key A[i+1] = A[i] i = i - 1 A[i+1] = key

堆排序(Heap Sort)

P99(84)

PARENT(i) return floor(i/2) LEFT(i) return 2i RIGHT(i) return 2i+1 MAX_HEAPIFY(A,i) l = LEFT(i) r = RIGHT(i) if l <= A.heap-size and A[l] > A[i] largest = l else largest = i if r <= A.heap-size and A[r] > A[largest] largest = r if largest != i swap(A[i], A[largest]) MAX_HEAPIFY(A, largest) BUILD_MAX_HEAP(A) A.heap-size = A.length for i = floor(A.length/2) downto 1 MAX_HEAPIFY(A,i) HEAPSORT(A) BUILD_MAX_HEAP(A) for i = A.length downto 2 swap(A[1], A[i]) A.heap-size = A.heap-size - 1 MAX-HEAPIFY(A,1)

快速排序(Quick Sort)

P110

QUICKSORT(A, p, r) if p < r q = PARTITION(A, p, r) QUICKSORT(A, p, q-1) QUICKSORT(A, q+1, r) PARTITION(A, p, r) x = A[r] i = p - 1 for j = p to r-1 if A[j] <= x i = i + 1 swap(A[i], A[j]) swap(A[i+1], A[r]) return i+1 RANDOMIZED_PARTITION(A, p, r) i = RANDOM(p, r) swap(A[r], A[i]) return PARTITION(A, p, r) RANDOMIZED_QUICKSORT(A, p, r) if p < r q = RANDOMIZED_PARTITION(A, p, r) RANDOMIZED_QUICKSORT(A, p, q-1) RANDOMIZED_QUICKSORT(A, q+1, r)

计数排序(Counting sort)

P124

//Assume all the numbers are integers between 0 and k. COUNTING_SORT(A, B, k) let C[0 .. k] be a new array for i = 0 to k C[i] = 0 for j = 1 to A.length C[A[j]] = C[A[j]] + 1 for i = 1 to k C[i] = C[i] + C[i-1] for j = A.length downto 1 B[C[A[j]]] = A[j] C[A[j]] = C[A[j]] - 1 RADIX_SORT(A, d) for i = 1 to d use a stable sort to sort array A on digit i //Assume all the number are doubles between 0 and 1. BUCKET_SORT(A) n = A.length let B[0 .. n-1] be a new array for i = 0 to n-1 make B[i] an empty list for i = 1 to n insert A[i] into list B[floor(nA[i])] for i = 0 to n-1 sort list B[i] with insertion sort concatenate the list B[0], B[1], ..., B[n-1] together in order

图算法

第六部分内容

广度优先搜索(BFS, Breadth-First Search)

P359 无注释版：

BFS（G, s） for each vertex u in G.V-{s} u.color = WHITE u.d = inf u.pi = NIL s.color = GRAY s.d = 0 s.pi = NIL Q = NULL ENQUEUE(Q, s) while Q != NULL u = DEQUEUE(Q) for each v in G.Adj[u] if v.color == WHITE v.color = GRAY v.d = u.d + 1 v.pi = u ENQUEUE(Q, v) u.color = BLACK

注释版：

BFS（G, s） //Graph:G and root vertex:s for each vertex u in G.V-{s} u.color = WHITE // set every vertex to Undiscovered State u.d = inf //distance from s to u u.pi = NIL //precedent vertex s.color = GRAY s.d = 0 s.pi = NIL //root vertex has been searched Q = NULL //First in, first out. ENQUEUE(Q, s) while Q != NULL u = DEQUEUE(Q) for each v in G.Adj[u] //Search EVERY adjacent vertex of u if v.color == WHITE //Undiscovered v.color = GRAY //Discovered but un-exausted v.d = u.d + 1 v.pi = u ENQUEUE(Q, v) u.color = BLACK //exausted

打印广度优先树(BFT)上的最短路径

P363

PRINT_PATH(G, s, v) if v == s print s else if v.pi == NIL print 'no path from' s 'to' v 'exists' else PRINT-PATH(G, s, v.pi) print v

深度优先搜索(Depth-First Search)

P365

DFS(G) for each vertex u in G.V u.color = WHITE u.pi = NIL time = 0 for each vertex u in G.V if u.color == WHITE DFS_VISIT(G, u) DFS_VISIT(G, u) time = time + 1 // White vertex u has just been discovered u.d = time //Discovered time u.color = GRAY for each v in G.Adj[u] // Explore edge (u,v) if v.color == WHITE //Undiscovered v.pi = u DFS_VISIT(G, v) u.color = BLACK // blacken u; it is finished time = time + 1 u.f = time //Finished time

拓扑排序(Topological Sort)

P371

TOPOLOGICAL_SORT(G) call DFS(G) to compute finishing times v.f for each vertex v as each vertex is finished, insert it onto the front of a linked list

强连通分量(Strongly Connected Components)

P372

STRONGLY_CONNECTED_COMPONENTS(G) call DFS(G) to compute finishing times u.f for each vertex u compute G^T call DFS(G^T),but in the main loop of DFS, consider the vertices in order of decreasing u.f (as computed in line 1) output the vertices of each tree in the depth-first forest formed in line3 as a separate strongly connected component

最小生成树(Minimum Spanning Tree)

P378

GENERIC_MST(G,w) A = EmptySet while A does not form a spanning tree find an edge(u,v) that is safe for A A = A U {(u,v)} return A

单源最短路径(Single Source Shortest Path)

P392

INITIALIZE_SINGLE_SOURCE(G,s) // s is the source vertex for each vertex v in G.V v.d = inf // v.distance from s (shortest) v.pi = NIL // v.father vertex s.d = 0 RELAX(u,v,w) if v.d > u.d + w(u,v) v.d = u.d + w(u,v) v.pi = u

Bellman-Ford 算法

P394

BELLMAN_FORD(G,w,s) INITIAZE_SINGLE_SOURCE(G,s) for i = 1 to |G.V|-1 for each edge(u,v) in G.E RELAX(u,v,w) for each edge(u,v) in G.E if v.d > u.d + w(u,v) //for negative-value Loop return FALSE return TRUE

有向无环图(DAG, Directed Acyclic Graph)中的单源最短路径问题

P396

DAG_SHORTEST_PATHS(G,w,s) topologically sort the vertices of G INITIALIZE_SINGLE_SOURCE(G,s) for each vertex u, taken in topologically sorted order for each vertex v in G.Adj[u] RELAX(u,v,w)

Dijkstras算法

P398

DIJKSTRA(G,w,s) INITIALIZE_SINGLE_SOURCE(G,s) S = EMPTY_SET // empty set Q = G.V while Q != EMPTY_SET u = EXTRACT_MIN(Q) S = S U {u} for each vertex v in G.Adj[u] RELAX(u,v,w)

节点对最短路径

打印最短路径

P414

PRINT_ALL_PAIRS_SHORTEST_PATH(Π,i,j) //前驱矩阵Π，存储了从i到j的最短路径中j的前驱节点pai[i][j] if i == j print i else if pai[i][j] == NIL print "no path from" i "to" j "exists" else PRINT_ALL_PAIRS_SHORTEST_PATH(Π,i,pai[i][j])

基于矩阵乘法的动态规划法(O(n⁴),O(n³lgn))

EXTEND_SHORTEST_PATHS(L,W) n = L.rows Let Lprim=(lprim[i][j]) be a new n*n matrix for i = 1 to n for j = 1 to n lprim[i][j] = Inf for k = 1 to n lprim[i][j] = min(lprim[i][j],l[i][k]+w[k][j]) return Lprim SQUARE_MATRIX_MULTIPLY(A,B) n = A.rows let C be a new n*n matrix for i = 1 to n for j = 1 to n c[i][j] = 0 for k = 1 to n c[i][j] = c[i][j] + a[i][k] * b[k][j] return C SLOW_ALL_PAIRS_SHORTEST_PATHS(W) n = W.rows L_1 = W for m = 2 to n-1 let L_m be a new n*n matrix L_m = EXTEND_SHORTEST_PATHS(L_m-1,W) return L_n-1 FASTER_ALL_PAIRS_SHORTEST_PATHS(W) n = W.rows L_1 = W m = 1 while m < n-1 let L_2m be a new n*n matrix L_2m = EXTEND_SHORTEST_PATHS(L_m,L_m) m = 2m return L_m

Floyd-Warshall算法(O(n³))

FLOYD_WARSHALL(W) n = W.rows D_0 = W for k = 1 to n let D_k = (d_k[i][j]) be a new n*n matrix for i = 1 to n for j = 1 to n d_k[i][j] = min(d_k-1[i][j],d_k-1[i][k]+d_k-1[k][j]) return D_n FLOYD_WARSHALL_PRIME(W) n = W.rows D = W for k = 1 to n for i = 1 to n for j = 1 to n d[i][j] = min(d[i][j],d[i][k]+d[k][j]) return D

构建传递闭包

TRANSITIVE_CLOSURE(G) n = |G.V| let T_0 = (t_0[i][j]) be a new n*n matrix for i = 1 to n for j = 1 to n if i == j or (i,j) in G.E t_0[i][j] = 1 else t_0[i][j] = 0 for k = 1 to n let T_k = (t_k[i][j]) be a new n*n matrix for i = 1 to n for j = 1 to n t_k[i][j] = t_k-1[i][j] ∪ (t_k-1[i][k] ∩ t_k-1[k][j]) return T_n

Johnson算法(O(n²lgn+VE))

散列表/哈希表(Hash table)

P157

直接寻址表(direct-address table)

DIRECT_ADDRESS_SEARCH(T, k) return T[k] DIRECT_ADDRESS_INSERT(T, x) T[x.key] = x DIRECT_ADDRESS_DELETE(T, x) T[x.key] = NIL

链接法(Chaining)解决冲突

P159

CHAINED_HASH_INSERT(T, x) insert x at the head of list T[h(x.key)] CHAINED_HASH_SEARCH(T, x) search for an element with key k in list T[h(k)] CHAINED_HASH_DELETE(T, x) delete x from the list T[h(x.key)]

开放寻址法(open addressing)

P167

HASH_INSERT(T, k) i = 0 repeat j = h(k,i) // <h(k,0),h(k,1),…，h(k,m-1)> 探查序列(probe sequence) if T[j] == NIL T[j] = k return j else i = i+1 until i == m error "hash table overflow" HASH_SEARCH(T, k) i = 0 repeat j = h(k,i) if T[j] == k return j i = i+1 until T[j] == NIL or i == m return NIL HASH_DELETE(T, k) //比较困难；故在必须删除关键字的应用中，常使用链接法来解决冲突