重複の可能性:
有向グラフでサイクルを検出するための最適なアルゴリズム
有向グラフでループを見つけるアルゴリズムを探しています。
私のグラフには、エッジではなくノードにのみラベルがあり、かなり巨大になる可能性があります。
アルゴリズムの出力は、一連のリストとしてのループである必要があります。各リストには、ループに含まれるノードのラベルが含まれている必要があります。したがって、リストの最初と最後の要素は同じである必要があります。
私が使用しているグラフには、連結成分が 1 つしかなく、強連結成分がない可能性が高いです。サイクル数は少ないと予想されます (まだ確認する必要があります)。
まさにこれまたは類似のもののための優れたアルゴリズムは大歓迎です。
どうもありがとうございました。
PS: 不明な点がある場合は、お気軽に詳細をお問い合わせください。たとえば、グラフは (これまでのところ) 1 つのノードから複数のノード (通常は 1 つ) までの一連のエッジとして保存されますが、これは無関係である必要があります。私見では。