1

有向グラフと、そのグラフのノードのセット U があります。セット U 内のすべてのノードを含むパス (単純なパスである必要はありません) があるかどうかを調べたいのですが、これを行う最も効率的な方法は何ですか?

4

1 に答える 1

0

ヒント: 元のグラフ G の e のソースから e のターゲットに到達できる場合は、e \in E' を使用してグラフ G'=(U,E') を作成します (到達可能性の正確な計算は、ノードへのアクセスを許可するかどうかによって異なります)。二回。）

では、問題を解決するために、G' について何を確認する必要がありますか?

于 2012-10-19T22:32:26.210 に答える