2

グラフの多くのアルゴリズムでは、通常、目的の結果の接続はparent配列に格納されます。

たとえば、BFS または DFS、最小スパニング ツリー、または最短パスでは、各頂点の親を に格納しparent[]ます。

私の質問は、そのような しかない場合、たとえば O(n) で任意の頂点parent[]間のパスを簡単に取得するにはどうすればよいですか? それがBFSかDFSか何かであるかどうかは問題ではないことに注意してください。重要なのはparent[]、グラフアルゴリズムから得られる唯一のものです。

頂点の 1 つが他の頂点の祖先である場合、パスを簡単に取得できます。それ以外の場合は、parent[]1 つの頂点からルートまでしかトレースバックできず、他の頂点についても同じことを行い、パスがどの祖先にあるかを確認します (ルート) マージ。これは、ある頂点の各祖先を別の頂点のすべての祖先と比較してマージ ポイントを探す必要があるため、O(n^2) になります。

誰でも助けることができますか？

4

6 に答える 6

5

サイズ N の bool 配列 A を使用すると、マージ ポイントを探す複雑さを解消できます。頂点 i からルートに移動するときに、途中の各頂点に対して A[i] = true とマークします。頂点 j からルートに移動するとき、A[i] == true の場合、それがマージ ポイント (最初のそのような頂点) です。

于 2012-05-02T11:56:07.923 に答える
3

この問題は、交差する 2 つのリンクされたリストから交差するノードを見つける問題のように聞こえます。このソリューションを確認してください2つの交差するリンクされたリストから交差するノードを見つける

于 2012-05-02T11:57:06.103 に答える
1

ツリー内のx、の間のパスを見つける： これは時間内に行うことができます。「k」はそれらの間の最短パスの長さです。各ノードに値0の整数auxを格納する代わりに。yT
O(k)O(n)

Climb up `x`'s and `y`'s ancestors simultaneously.  
Make each of `x`'s ancestors' aux = aux + 1  
Make each of `y`'s ancestors' aux = aux + 2

zそれらの間の最初の共通の祖先によって示します。xzで連結されたパスzyが最短パスになることに注意してくださいxy。

y'祖先がaux=3である場合、または'祖先が持つ場合x、に到達しましたz。

おそらく、一方が他方の祖先である場合を考慮して、これを修正する必要があります...また、頂点を順番に印刷するには、x'祖先をスタックに入れ、 y'祖先をキューに入れて、最後にそれらをポップアウトします。

于 2012-09-14T23:11:39.147 に答える
1 
// print the path between v1 and v2
w1 = v1
while w1 != root:
  ++n
  w1 = w1.parent

w2 = v2
while w2 != root:
  ++m
  w2 = w2.parent

if (m < n):
  swap(v1, v2)
  swap(m, n)

(m - n) times do:
  print v2
  v2 = v2.parent

while v1 != v2:
  print v2
  stack.push(v1)
  v1 = v1.parent
  v2 = v2.parent

while not stack.empty:
  print stack.pop
于 2012-05-02T11:55:07.173 に答える
0

あなたが言ったように、ルートから任意の頂点へのパスを簡単に取得できます。他の頂点からのパスが必要な場合は、その頂点をルートとして検索を再開する必要があります。これはアプローチではありませんO(n)が、得られる最善の方法のようです。(あるエッジに沿ったウェイが、同じエッジに沿った後方のウェイと同じ重みを持たないか、まったく存在しない場合を考えてみてください。)

于 2012-05-02T11:23:31.500 に答える
0

最も簡単な方法は、スタックを使用することです。このようなもの：

def getpath(parent, first, last):
     path = []
     while first != last:
         if last == None: # there isn't a path between first and last
             return None
         path.append(last)
         last = parent[last]
     path.append(first)
     path.reverse()
     return path
于 2012-05-02T11:32:21.423 に答える