data-structures
グラフトラバーサル
サーチ…
前書き
グラフトラバーサルに関連するすべてのアルゴリズム。ランタイムとスペースの両方の複雑さ
奥行き最初の検索
グラフのDepth First Traversal(またはSearch)は、ツリーのDepth First Traversalと似ています。ここでの唯一のキャッチは、ツリーとは異なり、グラフにサイクルが含まれる可能性があるため、同じノードに再び来ることがあります。ノードを複数回処理することを避けるために、boolean visited配列を使用します。
以下のアルゴリズムは、DFSを使用するグラフトラバーサルの手順を示しています。
アルゴリズムDFS(v);
入力 :グラフの頂点v
出力 :エッジの「検出」エッジおよび「バック」としてのラベル付けは、
for each edge e incident on v do
if edge e is unexplored then
let w be the other endpoint of e
if vertex w is unexplored then
label e as a discovery edge
recursively call DFS(w)
else
label e as a backedge
幅広い検索
アルゴリズムBFS(G)
入力グラフG
Gの頂点のエッジと区画の出力ラベル
for all u ∈ G.vertices()
setLabel(u, UNEXPLORED)
for all e ∈ G.edges()
setLabel
(e, UNEXPLORED)
for all v ∈ G.vertices()
if getLabel(v) = UNEXPLORED
BFS(G, v)
Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow