徹底的に検索します。 DFS


DFS DFS
深さ優先検索 (DFS) は、グラフに関する主要なアルゴリズムの 1 つです。アルゴリズムは O(N + M) で実行されます。
 
アルゴリズム
まず、トップから始めて、このトップの子を考えます。まだ入力していない場合は、それらから DFS を開始します。


Training problem

DFS: はじめに (C++)

DFS DFS
深さ優先検索 (DFS) は、グラフに関する主要なアルゴリズムの 1 つです。アルゴリズムは O(N + M) で実行されます。
 
アルゴリズム
まず、トップから始めて、このトップの子を考えます。まだ入力していない場合は、それらから DFS を開始します。


Training problem

DFS: 開始 (Python)

二部グラフ
 
二部グラフ - 頂点が 2 つのセットに分割され、各エッジが異なるセットからの頂点。


多くの場合、2 部グラフのコンテキストでは、 色 頂点の概念が使用されます。グラフを 2 つの部分に分割することを、頂点を 2 つの異なる色で色付けすると呼びます。各エッジは、異なる色の頂点を接続する必要があります。

DFS. 
 

アルゴリズム

任意の頂点からペイントを開始し、任意の色でペイントします。
各エッジを通過するとき、次の頂点を反対の色でペイントします。
隣接する頂点を繰り返し処理しているときに、現在の色と同じ色で既にペイントされている頂点が見つかった場合、グラフに奇数のサイクルがあり、2 部構成ではないことを意味します。

Training problem

二部グラフ

アルゴリズムは次のように説明できます:
n 個の頂点と m 個のエッジを持つ有向グラフが与えられます。各エッジが小さい番号の頂点から大きい番号の頂点につながるように、頂点の番号を付け直す必要があります。
言い換えれば、グラフのすべての辺によって与えられる順序に対応する頂点の順列 (トポロジカル順序) を見つける必要があります。
深さ優先検索 (dfs(v)) を使用します
\(dfs(v)\)  から終了するときにリストの先頭に頂点を追加すると、最後にこのリストでは、トポロジカルなソートが得られます。
したがって、目的のトポロジー ソート —これは退出時間の降順で並べ替えられています。

Training problem

トポロジカルソート