荷物のネットワークには、ループ、重複した路線、路線のないデポが含まれることがあります。走査には、何をすでに訪れたかについての明確な規則が必要です。頂点はキューに追加するときに印を付け、別の入ってくる路線から再び追加されないようにします。すべての辺のコストが1のとき、幅優先探索は頂点を距離の順に処理します。
1つの開始点からの探索で、その連結成分の中での到達可能性の問いに答えられます。ネットワーク全体を調べるには、すべての識別子を走査し、まだ見ていない頂点ごとに探索をやり直します。状態の意味を明確に保ってください:訪問済みフラグは到達可能性に答え、距離は乗り継ぎの回数を記録し、色は2つのシフトへの割り当てを表します。まずガイド付きでキューの組み立てから始め、次に同じ探索の考え方を非連結のグラフや衝突する制約に使い回します。