グラフの多くのアルゴリズムでは、通常、目的の結果の接続はparent
配列に格納されます。
たとえば、BFS または DFS、最小スパニング ツリー、または最短パスでは、各頂点の親を に格納しparent[]
ます。
私の質問は、そのような しかない場合、たとえば O(n) で任意の頂点parent[]
間のパスを簡単に取得するにはどうすればよいですか? それがBFSかDFSか何かであるかどうかは問題ではないことに注意してください。重要なのはparent[]
、グラフアルゴリズムから得られる唯一のものです。
頂点の 1 つが他の頂点の祖先である場合、パスを簡単に取得できます。それ以外の場合は、parent[]
1 つの頂点からルートまでしかトレースバックできず、他の頂点についても同じことを行い、パスがどの祖先にあるかを確認します (ルート) マージ。これは、ある頂点の各祖先を別の頂点のすべての祖先と比較してマージ ポイントを探す必要があるため、O(n^2) になります。
誰でも助けることができますか?