Detect Cycle in a Directed Graph

959 ワード
Graph Graph Cycle テキストリンク
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)の論理のようにループが存在する.
(55) 61 3142 0720 Como ligar para a TAP Portugal do Brasil?
ベストアルバム|プログラマーlv 3