0

G=(V,E) が有向グラフである場合、次のことを行うには、BFS または DFS からアルゴリズムを設計する必要があります。

sから V 内の他の頂点 u への単純なパスが最大で 1 つあるかどうかを確認します。このアルゴリズムは O(|V|+|E|) 上にある必要があります。

また、前のアルゴリズムから、別の O(|V||E|) アルゴリズムを設計して、任意の 2 つの頂点uとvの間に最大で 1 つの単純なパスがあるかどうかを確認する必要があります。

あなたが私を助けてくれることを願っています！よろしくお願いします！

4

1 に答える 1

2

ヒント: sからuへのパス上のすべてのエッジがカット エッジ(ブリッジ) である場合はどうなりますか? それらのいずれかが最先端でない場合はどうなりますか? :)

注: グラフ O(V+E) 時間ですべての橋を見つけることができます

于 2013-07-07T13:24:28.753 に答える