BFS(G, s) for 各頂点 u ∈ G.V - {s} u.color = WHITE u.d = ∞ u.π = NIL s.color = GRAY s.d = 0 s.π = NIL Q = ∅ ENQUEUE(Q, s) while Q != ∅ u = DEQUEUE(Q) for 各頂点 v ∈ G.Adj[u] // uの近傍を探索する if v.color == WHITE // vが今発見されている？ v.color = GRAY v.d = u.d + 1 v.π = u ENQUEUE(Q, v) // vが今最前線上にある u.color = BLACK // uは今最前線の後方にある
手続きPRINT-PATHは、sからvへの最短路上の頂点をプリントする
1 2 3 4 5 6 7
PRINT-PATH(G, s, v) if v == s sをプリントする elseif v.π == NIL s “から” v “への経路は存在しない”をプリントする else PRINT-PATH(G, s, v.π) vをプリントする
compute a path in that
traverses each edge in exactly
once in each direction
1 2 3 4 5 6 7
MAKE-PATH(u) for each v ∈ Adj[u] but not in the tree such that u ≤ v go to v and back to u for each v ∈ Adj[u] but not equal to u.π go to v perform the path proscribed by MAKE-PATH(v) go to u.π
DFS(G) for 各頂点 u ∈ G.V u.color = WHITE u.π = NIL time = 0 // cc = 1 for 各頂点 u ∈ G.V if u.color == WHITE // u.cc = cc // cc = cc + 1 DFS-VISIT(G, u)
1 2 3 4 5 6 7 8 9 10 11 12
DFS-VISIT(G, u) time = time + 1// 白頂点uが今発見された u.d = time u.color = GRAY for 各頂点 v ∈ G.Adj[u] // 各辺(u, v)を探索する if v.color == WHITE // v.cc = u.cc v.π = u DFS-VISIT(G, v) time = time + 1 u.f = time u.color = BLACK // uを黒に彩色する；uの探索が終了した
再帰を使わず、スタックを用いるDFS
1 2 3 4 5 6 7 8
DFS-STACK(G) for each vertex u ∈ G.V u.color = WHITE u.π = NIL time = 0 for each vertex u ∈ G.V if u.color == WHITE DFS-VISIT-STACK(G, u)
DFS-VISIT-STACK(G, u) S = Ø PUSH(S, u) time = time + 1// 白頂点uが今発見された u.d = time u.color = GRAY while !STACK-EMPTY(S) u = TOP(S) v = FIRST-WHITE-NEIGHBOR(G, u) if v == NIL // uの隣接リストは十分に探索された POP(S) time = time + 1 u.f = time u.color = BLACK // uを黒に彩色する；uの探索が終了した else // uの隣接リストはまだ探索されていない v.π = u time = time + 1 v.d = time v.color = GRAY PUSH(S, v)
1 2 3 4 5
FIRST-WHITE-NEIGHBOR(G, u) for each vertex v ∈ G.Adj[u] if v.color == WHITE return v return NIL
有向グラフGの全ての辺をその種類と共に印刷するバージョン
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
DFS-VISIT-PRINT(G, u) time = time + 1 u.d = time u.color = GRAY for each vertex v ∈ G.Adj[u] if v.color == WHITE print "(u, v) is a tree edge." v.π = u DFS-VISIT-PRINT(G, v) elseif v.color == GRAY print "(u, v) is a back edge." elseif v.d > u.d print "(u, v) is a forward edge." else print "(u, v) is a cross edge." u.color = BLACK time = time + 1 u.f = time
SIMPLE-PATHS(G, u, v) TOPOLOGICAL-SORT(G) let {v[1], v[2]..v[k - 1]} be the vertex between u and v v[0] = u v[k] = v for j = 0 to k - 1 DP[j] = ∞ DP[k] = 1 return SIMPLE-PATHS-AID(G, DP, 0)
1 2 3 4 5 6 7 8 9 10
SIMPLE-PATHS-AID(G, DP, i) if i > k return0 elseif DP[i] != ∞ return DP[i] else DP[i] = 0 for v[m] in G.adj[v[i]] and 0 < m ≤ k DP[i] += SIMPLE-PATHS-AID(G, DP, m) return DP[i]
MST-KRUSKAL(G, w) A = ∅ for 各頂点 v ∈ G.V MAKE-SET(v) G.Eの辺を含む1つのリストを生成する 重みwの単調増加順にG.Eの辺のリストをソートする for ソートされたリストから順に各辺(u, v) ∈ G.E if FIND-SET(u) != FIND-SET(v) A = A ∪ {(u, v)} UNION(u, v) return A
MST-PRIM(G, w, r) for 各頂点 u ∈ G.V u.key = ∞ u.π = NIL r.key = 0 Q = ∅ for 各頂点 u ∈ G.V INSERT(G, u) while Q != ∅ u = EXTRACT-MIN(Q) for G.Adj[u]の各頂点v if v ∈ Q and w(u, v) < v.key v.π = u v.key = w(u, v) DECREASE-KEY(Q, v, w(u, v))
グラフが隣接行列によって与えられるとき、時間で走るPrimのアルゴリズム
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
PRIM-ADJ(G, w, r) initialize A with every entry = (NIL, ∞) T = {r} for i = 1 to V if Adj[r, i] != 0 A[i] = (r, w(r, i)) while T != V min = ∞ for each v in V - T if A[v].2 < min min = A[v].2 k = v T = T ∪ {k} k.π = A[k].1 for i = 1 to V if Adj[k, i] != 0 and i ∉ T and w(k, i) < A[i].2 A[i] = (k, w(k, i))
BELLMAN-FORD(G, w, s) INITIALIZE-SINGLE-SOURCE(G, s) for i = 1 to |G.V| - 1 for 各辺 (u, v) ∈ G.E RELAX(u, v, w) for 各辺 (u, v) ∈ G.E if v.d > u.d + w(u, v) return FALSE return TRUE
始点から頂点vへのある経路上に負閉路があるとき、v.d値として-∞を設定するバージョン
1 2 3 4 5 6 7 8 9 10
BELLMAN-FORD`(G, w, s) INITIALIZE-SINGLE-SOURCE(G, s) for i = 1 to |G.V| - 1 for each edge (u, v) ∈ G.E RELAX(u, v, w) for each edge(u, v) ∈ G.E if v.d > u.d + w(u, v) mark v for each vertex u ∈ marked vertices DFS-MARK(u)
1 2 3 4 5
DFS-MARK(u) if u != NIL and u.d != -∞ u.d = -∞ for each v in G.Adj[u] DFS-MARK(v)
DIJKSTRA(G, w, s) INITIALIZE-SINGLE-SOURCE(G, s) S = ∅ Q = ∅ for 各頂点 u ∈ G.V INSERT(Q, u) while Q != ∅ u = EXTRACT-MIN(Q) S = S ∪ {u} for 各頂点 v ∈ G.Adj[u] RELAX(u, v, w) if RELAXがv.d値を減少させる DECREASE-KEY(Q, v, v.d)
FLOYD-WARSHALL(W, n) D(0) = W for k = 1 to n D(k) = (d[i, j](k))は新しい n x n 型行列である for i = 1 to n for j = 1 to n d[i, j](k) = min{ d[i, j](k - 1), d[i, k](k - 1) + d[k, j](k - 1) } return D^(n)
式(23.7)と式(23.8)に従って行列π(k)を計算するバージョン
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
MOD-FLOYD-WARSHALL(W) n = W.rows D(0) = W let π(0) be a new n × n matrix for i = 1 to n for j = 1 to n if i != j and D[i, j](0) < ∞ π[i, j](0) = i for k = 1 to n let D(k) be a new n × n matrix let π(k) be a new n × n matrix for i = 1 to n for j = 1 to n if d[i, j](k - 1) ≤ d[i, k](k - 1) + d[k, j](k - 1) d[i, j](k) = d[i, j](k - 1) π[i, j](k) = π[i, j](k - 1) else d[i, j](k) = d[i, k](k - 1) + d[k, j](k - 1) π[i, j](k) = π[k, j](k - 1)