グラフの走査

深さ優先と幅優先は、グラフを走査する 2 つの一般的な方法です。
グラフ トラバーサル は、グラフ内の各頂点を 1 回だけ訪問するプロセスです。グラフを走査するには 2 つの一般的な方法があります。深さ優先走査 (または 深さ優先検索) と 幅優先走査 (または 幅-最初の検索)。どちらの走査も結果としてスパニング ツリーを生成します。これは、次の図に示すように、クラスを使用してモデル化できます。 Tree は、AbstractGraph クラスで定義された内部クラスであることに注意してください。 AbstractGraph.Tree は、要素の検索で定義された Tree インターフェイスとは異なります。 AbstractGraph.Tree はノードの親子関係を記述するために設計された特殊なクラスですが、Tree インターフェイスはツリー内の検索、挿入、削除などの一般的な操作を定義します。スパニング ツリーに対してこれらの操作を実行する必要がないため、AbstractGraph.Tree は Tree のサブタイプとして定義されません。

Tree クラスは、AbstractGraph.java の行 226 ～ 293 で AbstractGraph クラスの内部クラスとして定義されています。コンストラクターは、ルート、エッジ、検索順序を含むツリーを作成します。

Tree クラスは 7 つのメソッドを定義します。 getRoot() メソッドはツリーのルートを返します。 getSearchOrder() メソッドを呼び出すことで、検索された頂点の順序を取得できます。 getParent(v) を呼び出して、検索で頂点 v の親を見つけることができます。 getNumberOfVerticesFound() を呼び出すと、検索された頂点の数が返されます。メソッド getPath(index) は、指定された頂点インデックスからルートまでの頂点のリストを返します。 printPath(v) を呼び出すと、ルートから v までのパスが表示されます。 printTree() メソッドを使用して、ツリー内のすべてのエッジを表示できます。

以上がグラフの走査の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。