0

以下は、バック エッジとツリー エッジをマークするためのロジックを含む DFS の一般的なコードです。私の疑問は、頂点からのバックエッジが戻って先祖を指し、親を指すバックエッジではないということです（無向グラフを想定しましょう）。無向グラフでは、2 つの頂点 x と y の間を前後にエッジがあります。したがって、y を処理するときに x にアクセスした後、y は隣接する頂点として x を持ちますが、既にアクセスしているため、コードはそれをバック エッジとしてマークします。

私がそう言うのは正しいですか？私の仮定が有効な場合に備えて、これを回避するために追加のロジックを追加する必要がありますか?

DFS(G)
for v in vertices[G] do
    color[v] = white    
    parent[v]= nil
    time = 0        

for v in vertices[G] do
    if color[v] = white then
    DFS-Visit(v)

Induce a depth-rst tree on a graph starting at v.

DFS-Visit(v)
    color[v]=gray
    time=time + 1
    discovery[v]=time
    for a in Adj[v] do
       if color[a] = white then
        parent[a] = v
        DFS-Visit(a)
        v->a is a tree edge
       elseif color[a] = grey then  
        v->a is a back edge
    color[v] = black
    time = time + 1

白い意味unexplored、灰色の意味frontier、黒の意味processed

4

1 に答える 1

0

はい、この実装はfrontier色 (訪問済み、未訪問) のみでノードを決定するため、親ノードと祖先ノードを分離しません。したがって、DFS 検索ツリーの各エッジはバック エッジとしてマークされます。

ツリーとバック エッジを分離するには、エッジを親ノードと祖先ノードに分離する必要があります。簡単な方法は、親ノードをパラメーターとして DFS-Visit ( p) に提供することです。例えば：

DFS-Visit(v, p)
 color[v]=gray
 time=time + 1
 discovery[v]=time
 for a in Adj[v] do
   if color[a] = white then
       parent[a] = v
       DFS-Visit(a,v)
       v->a is a tree edge
   elseif color[a] = grey and (a is not p) then
       v->a is a back edge
 color[v] = black 
 time = time + 1

更新:親ノードを既に保存していることに気づいていません。したがって、パラメーターを導入する必要はありません。

DFS-Visit(v)
 color[v]=gray
 time=time + 1
 discovery[v]=time
 for a in Adj[v] do
   if color[a] = white then
       parent[a] = v
       DFS-Visit(a)
       v->a is a tree edge
   elseif color[a] = grey and (a is not parent[v]) then
       v->a is a back edge
 color[v] = black 
 time = time + 1
于 2012-12-12T07:53:32.533 に答える