データ構造でのグラフの検索
グラフで検索するには、2つの異なる方法があります。幅優先探索と深さ優先探索の手法。
幅優先探索（BFS）
幅優先探索（BFS）トラバーサルはアルゴリズムであり、特定のグラフのすべてのノードにアクセスするために使用されます。このトラバーサルアルゴリズムでは、1つのノードが選択され、隣接するすべてのノードが1つずつ訪問されます。隣接するすべての頂点を完了すると、さらに移動して別の頂点をチェックし、隣接する頂点を再度チェックします。このアルゴリズムを実装するには、キューデータ構造を使用する必要があります。隣接するすべての頂点が完了すると、隣接するすべての頂点がキューに追加され、1つのアイテムがキューから削除され、その頂点を再び通過し始めます。
深さ優先探索（DFS）
深さ優先探索（DFS）は、グラフ走査アルゴリズムです。このアルゴリズムでは、開始頂点が1つ与えられ、隣接する頂点が見つかると、最初にその隣接する頂点に移動し、同じ方法でトラバースを試みます。可能な限り深さ全体を移動し、その後、バックトラックして前の頂点に到達し、新しいパスを見つけます。
DFSを反復的に実装するには、スタックデータ構造を使用する必要があります。再帰的に実行する場合は、外部スタックは必要ありません。再帰呼び出しの内部スタックで実行できます。
-
データ構造の区間木
このセクションでは、区間木とは何かを確認します。名前が示すように、区間木は区間に関連付けられている木です。したがって、区間木について説明する前に、基本的な区間を見てみましょう。 間隔は基本的に範囲です。したがって、1つの間隔が[a、b]と記述されている場合、範囲がaから始まり、bで終わることを示します。 ここで、間隔[10、20]があるとします。したがって、3つの範囲値があります。最初は-∞から10、10から20、最後は20から∞ ここで、[15、25]から2番目の間隔を作成するとします。したがって、これは次のようになります- [18、22]から別の間隔を作ると、次のようにな
-
ハーフエッジデータ構造
はじめに テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。 ハーフエッジデ