EULER-CYCLE-UNDIRECTED-DFS(G, A, u) while G.Adj[u] != ∅ select v from G.Adj[u] randomly and remove it from G.Adj[u] remove a u from G.Adj[v] dfs(v) INSERT(A, u)
EULER-CYCLE-UNDIRECTED(G) select s ∈ G.V randomly Let A be new array EULER-CYCLE-DFS(G, A, s) reverse A return A
GEN-DISJOINT-PERFECT-MATCHING-AUX(G, A) if |G.E| * 2 == |G.V| INSERT(A, G.E) else E1 = Ø E2 = Ø P = EULER-CYCLE-UNDIRECTED(G) for i = 2 to P.size if i % 2 == 0 E1 = E1 ∪ {P[i - 1], P[i]} else E2 = E2 ∪ {P[i - 1], P[i]} GEN-DISJOINT-PERFECT-MATCHING-AUX((G.V, E1), A) GEN-DISJOINT-PERFECT-MATCHING-AUX((G.V, E2), A) GEN-DISJOINT-PERFECT-MATCHING(G) Let A be a new array GEN-DISJOINT-PERFECT-MATCHING-AUX(G, A)
FIND-AUGMENTING-PATH'''(w, n, h, match) Q = Ø FL = Ø FR = Ø for each unmatched vertex l ∈ L l.π = NIL ENQUEUE(Q, l) FL = FL ∪ {l} for each vertex r in R r.δ = min{h[l] + h[r] − w(l, r) : l ∈ FL} repeat if Q is empty δ = min { h[l] + h[r] − w(l, r) : l ∈ FL and r ∈ R − FR } for each vertex l ∈ FL h[l] = h[l] − δ for each vertex r ∈ FR h[r] = h[r] + δ for each vertex r ∈ R - FR r.δ = r.δ - δ if r.δ == 0 for each l ∈ FL if h[l] + h[r] == w(l, r) r.π = l break if match[r] == 0 // 代表r仍然未被匹配 an M-augmenting path has been found (exit the repeat loop) else ENQUEUE(Q, r) FR = FR ∪ {r} u = DEQUEUE(Q) if 1 <= u <= n // 这时u是左部节点 for r = n + 1 to n + n if h[u] + h[r] == w(u, r) and r ∉ FR r.π = u if match[r] == 0 an M-augmenting path has been found (exit the repeat loop) else ENQUEUE(Q, r) FR = FR ∪ {r} else // 这时u是右部节点 l = match[u] l.π = u FL = FL ∪ {l} ENQUEUE(Q, l) for each vertex r ∈ R - FR r.δ = min{r.δ, l[h] + r[h] - w(v, r)} until an M-augmenting path has been found using the predecessor attributes π, construct an M-augmenting path P by tracing back from the unmatched vertex in R return P
在程序 FIND-AUGMENTING-PATH''' 的 repeat ... until 循环中,所有的 for 循环都是线性的。中间那个用于更新 中每个节点的 属性的 for 循环中,内部的 for 循环每个节点 节点最多只能进入一次,然后要么找到了增广路径,repeat ... until 跳出,要么被添加进集合 中,之后再也不会进入。除此之外,repeat ... until 循环体内的其它所有 for 循环都是单层的。因此一次 repeat ... until 循环的时间复杂度为,调用一次 FIND-AUGMENTING-PATH''' 所需要花费的时间为。
GEN-INTEGER-MATCHING(G, x) while the edge set H = {(u, v) |(u, v) ∈ G.E, 0 < x(u, v) < 1} still contain a cycle C generate the directed cycle C' from C EL = {(l, r) ∣ (l, r) ∈ C', l ∈ L, r ∈ R} ER = H - EL δ = min{x(l, r) ∣ (l, r) ∈ ER} for each edge (u, v) in EL x(u, v) = x(u, v) + δ for each edge (u, v) in ER x(u, v) = x(u, v) - δ while the longest path length of (V, H) exceeds 2 let a - b - c be a path of length of 2 s.t. a incident only once in H x(a, b) = x(a, b) + x(b, c) x(b, c) = 0 E = Ø for each edge (u, v) in G.E if x(u, v) > 0 E = E ∪ {(u, v)} return E
UPDATE-X-FRACTIONAL-MATCHING(C, x, w) generate the directed edges set C' from C s.t. all of the edges in the same direction EL = {(l, r) ∣ (l, r) ∈ C', l ∈ L, r ∈ R} ER = H - EL SL = 0 SR = 0 for each edge (u, v) in EL SL = SL + w(u, v) for each edge (u, v) in ER SR = SR + w(u, v) if SL > SR δ = min{x(l, r) ∣ (l, r) ∈ ER} for each edge (u, v) in EL x(u, v) = x(u, v) + δ for each edge (u, v) in ER x(u, v) = x(u, v) - δ else δ = min{x(l, r) ∣ (l, r) ∈ EL} for each edge (u, v) in ER x(u, v) = x(u, v) + δ for each edge (u, v) in EL x(u, v) = x(u, v) - δ GEN-INTEGER-MATCHING(G, x, w) while the edge set H = {(u, v) |(u, v) ∈ G.E, 0 < x(u, v) < 1} still contain a cycle C UPDATE-X-FRACTIONAL-MATCHING(C, x, w) while the longest path P length of (V, H) exceeds 2 UPDATE-X-FRACTIONAL-MATCHING(P, x, w) E = Ø for each edge (u, v) in G.E if x(u, v) > 0 E = E ∪ {(u, v)} return E