DFSの反復バージョンを使用して有向グラフのサイクルを検出する方法はありますか？

Question

再帰的DFSでは、ノードをWHITE,GRAYおよびBLACKのように塗りつぶして、サイクルを検出することができます（here）。

DFS検索中にGRAYノードが検出された場合、サイクルが存在します。

質問：DFSのこの反復バージョンでノードをGRAYとBLACKと表示するのはいつですか？ DFSで

1 procedure DFS-iterative(G,v): 
    2  let S be a stack 
    3  S.push(v) 
    4  while S is not empty 
    5   v = S.pop() 
    6   if v is not labeled as discovered: 
    7    label v as discovered 
    8    for all edges from v to w in G.adjacentEdges(v) do 
    9     S.push(w) 

Answer 1

1つのオプションは、情報を入力または終了する場合に、情報に沿って各ノードをスタックに2回プッシュすることです。スタックからノードをポップすると、あなたが出入りしているかどうかをチェックします。色を入力すると灰色になり、再び積み重ねて隣人に進む。出口の場合は、ただ黒く塗ります。

from collections import defaultdict 

WHITE = 0 
GRAY = 1 
BLACK = 2 

EDGES = [(0, 1), (1, 2), (0, 2), (2, 3), (3, 0)] 

ENTER = 0 
EXIT = 1 

def create_graph(edges): 
    graph = defaultdict(list) 
    for x, y in edges: 
     graph[x].append(y) 

    return graph 

def dfs_iter(graph, start): 
    state = {v: WHITE for v in graph} 
    stack = [(ENTER, start)] 

    while stack: 
     act, v = stack.pop() 

     if act == EXIT: 
      print('Exit', v) 
      state[v] = BLACK 
     else: 
      print('Enter', v) 
      state[v] = GRAY 
      stack.append((EXIT, v)) 
      for n in graph[v]: 
       if state[n] == GRAY: 
        print('Found cycle at', n) 
       elif state[n] == WHITE: 
        stack.append((ENTER, n)) 

graph = create_graph(EDGES) 
dfs_iter(graph, 0) 

出力：

Enter 0 
Enter 2 
Enter 3 
Found cycle at 0 
Exit 3 
Exit 2 
Enter 1 
Exit 1 
Exit 0 

ここ

は簡単なグラフのサイクルを検出し、短いPythonのデモです

Answer 2

（ウィキペディアから）、枝の終わりには、これらのノードがブラックある子を持たないというのノードです。次に、これらのノードの親をチェックします。親にGray子供がいない場合は黒です。同様に、黒色をノードに設定し続けると、すべてのノードの色が黒になります。

たとえば、DFSを以下のグラフで実行します。

DFSuから始まり、u -> v -> y -> xを訪問しました。 xには子がありません。このノードの色をの黒色のに変更する必要があります。

discovery timeに従って訪問先パスのxの親に戻ります。したがって、xの親はyです。 yにはGrayという色の子がありません。したがって、このノードの色をの黒色のに変更する必要があります。