mysql - MySQL での深さ優先検索

Question

エッジとエッジ セットを入力としてPROCEDURE取り、ブール値を出力して、追加のエッジが循環グラフになるかどうかを判断するMySQL を作成しようとしています。「 」のような列を持つすべての頂点のテーブルを作成し、エッジセットを実行中に頂点が複数回アクセスされたかどうかを確認する以外に、これを行うより簡単な方法はありますか?eesetiscyclicvisit count

Answer 1

Billiska のコメントが示すように、フォレストの個々のツリー、つまり接続されたセットを追跡する必要があります。

素集合データ構造の最も簡単な実装は、IDすべての頂点の をID親のにマップする単一の一時テーブルで構成されます。ある頂点から次の頂点へとこれらの親リンクをたどることができ、最終的にこのツリーのルート (自分自身を指す頂点) にたどり着きます。このルートは、接続されたセット全体を識別する一意の代表として機能します。

したがって、2 つのセットが既に接続されているかどうかを確認するには、それらの根を計算して単純に比較します。

• 最初は、すべての頂点が独自の親です。
• 2 つのノードの接続は、それらのルートを計算し、一方を他方の親にすることによってモデル化されます。

ツリーの深さを低く保つ追加のツールがあります。

• 常に深いツリーを深いツリーの親にし、パス圧縮を実行して見つかったノードの深さを減らすことができます。

これらはすべて MySQL でもモデル化できますが、パフォーマンスの動作はインメモリ実装とは異なる場合があります。

したがって、より多くのパフォーマンスが必要であり、さまざまな実装をテストして比較するためのデータが得られるまで、それを延期することをお勧めします。