Depth First Search GraphでTreeを作成できます.このとき、この木にbackedgeが存在すると、ループがあると言います
Treeでは、Back Edgeは、現在のノードからその祖先ノードへのedgeを指す.(自分も含めて)
Cycleを見つけるにはどうすればいいですか?

Solutions

DFSはStackを使用します.このとき、ループを持つGraphでループを行うと、back edgeのために現在のスタック内のノードに再アクセスします.これを確認すればいいのですが、方法はいろいろあります.

solution 1)

Stack上のノードにアクセスしていることを確認するには、Bool arrayを追加して、そのノードがStack上にあるかどうかを確認します.

solution 2)

第2の方法は、従来のDFSで使用されているアクセスを変換することである.既存のアクセス者は、アクセスしたノードとアクセスしていないノードを区別するために2つの色を使用します.この変形を,アクセスにはcolorを用いる方法が3つある.

1. White: 처리되지 않음.
2. Gray: 처리중.
3. Black: 처리 완료. 즉, 모든 인접 nodes 방문 완료.

現在のステータスがグレーのnodeはスタックにあります.すなわち,灰色のノードに近づくと,ソリューション1)の論理のようにループが存在する.