サーチ…


前書き

グラフトラバーサルに関連するすべてのアルゴリズム。ランタイムとスペースの両方の複雑さ

奥行き最初の検索

グラフの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

DFSイラストレーション

ここに画像の説明を入力

幅広い検索

アルゴリズム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