data-structures - グラフでの無効なパスの定義

Question

通常の有向グラフがほとんどの場合に適しているというプロジェクトに取り組んでいます。ただし、グラフでは、いくつかのパスを無効にしたいと考えています。たとえば、グラフが次の場合:

A->B
A->D
B->C
D->C

次に、A->B->C は有効なパスですが、A->D->C は有効ではありません。どこかに無効なパスを定義し、毎回検証チェックを行うこともできますが、アプリケーションはグラフに大きく依存しているため、これは重大なパフォーマンスの問題を引き起こします。

では、このタイプの状況に対応する特別なデータ構造またはアルゴリズムはありますか?

ありがとう

Answer 1

の各ノードにマッピングを保存するfrom:list(to)と、C から移動できるノードのリストにないため、A からのパスが C に移動できないことがわかります。深さが 1 より大きい場合、それまでのノードのタプルは、その 1 つのノードの代わりにキーになることができます。これは、eBGP がインターネット ルーティングでどのように機能するかによく似ています。

別の注意として、説明しているようなデータ構造を使用することにした場合は、何があってもチェックを行う必要があります。それか、状況ごとに複数のグラフを保存します。