グラフ - すでに2つの頂点間のパスを印刷する方法

Question

グラフの多くのアルゴリズムでは、希望の結果の接続は通常parentアレイに格納されます。

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

私の質問は私だけなparent[]を持っている場合、どのように私は簡単にO（n）の中で任意の頂点、たとえば、間のパスを取得することができるということですか？それはBFSまたはDFSか何か問題ではないことに注意してください。重要なのはparent[]です。私はグラフアルゴリズムの形を取っています。

頂点の1つが他の頂点であれば、簡単にパスを取得できます。そうでない場合は、parent[]を経由して1つの頂点からルートにトレースし、もう一度他の頂点に対して行います。祖先のルート（ルートに）がマージされます。そして、この結果はO（n^2）になります。なぜなら、ある頂点の各祖先を別の頂点のすべての祖先と比較してマージポイントを求める必要があるからです。

誰でも手助けできますか？

Answer 1

この問題は、交差する2つのリンクされたリストから交差ノードを見つける問題のように聞こえます。 、ツリーTにx、y間のパスを見つけるこのソリューションFinding the intersecting node from two intersecting linked lists

Answer 2

あなたが言ったように、ルートから任意の頂点までのパスを簡単に取得できます。他の頂点からのパスが必要な場合は、その頂点をルートとして検索を再開する必要があります。これはO(n) - 接近ではありませんが、あなたが得ることができる最高のようです。 （あるエッジに沿ったウェイが、同じエッジに沿ったウェイと同じウェイトを持っていないか、まったく存在しない場合を考慮してください）。

Answer 3

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

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 

Answer 4

// 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 

Answer 5

あなたはサイズNのブール配列Aを使用する場合は、頂点から行くときは、私は、ルートに、マークAをマージポイントを求めているの複雑さを排除することができます[I]途中の各頂点について真=真。頂点jからルートに行くとき、A [i] == trueならば、それがマージポイント（最初の頂点）です。

Answer 6

を確認してください：
あなたは時間O(k)でこれを行うことができ、それらの間の最短経路の長さ「K」。 O(n)の代わりに、各ノードに値0の整数auxを格納します。

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によって、それらの間の第1の共通の祖先を表します。パスxzをzyと連結すると、最短パスはxyになります。

yの祖先がaux = 3の場合、またはxの祖先が行う場合は、zに達しています。

これらのうちの1つが相手の祖先である場合は、おそらくアカウントに修正する必要があります。頂点を順番に印刷する場合は、xの先祖をスタックに入れ、先祖の先祖の先祖を待ち行列に入れて最後に出す必要があります。