algorithm - Tarjan のアルゴリズムにおけるクロスリンク

Question

scc に関する Tarjan の論文を読んでいます。

この論文では、特定の頂点のローリンクは次のように定義されています。

LOWLINK (v) は、v と同じコンポーネント内にある最小の頂点であり、0 個以上のツリー アークとそれに続く多くても 1 つのリーフまたはクロス リンクをトラバースすることによって到達できます。

特定の scc 内の 2 つの頂点からクロス リンク エッジを経由するパスの状況を思いつくことはできません。これは、scc 全体が dfs 検索によって派生した 1 つのツリー内にある必要があるためです。誰かがこれを少し説明できますか？

Answer 1

アイデアは簡単です：

グラフをトラバースするときにインデックスを付けます。再帰から戻るときに、ノードごとに、そこから到達可能な最小のインデックスをメモします。指定されたノードが既に持っているよりも低いインデックスに到達するには、クロス リンクまたはフロント リンクが必要です。より低いインデックスでまだ開いているノードに到達すると、同じ scc でノードが見つかったことを意味するため、同じローリンクを持つすべてのノードが同じコンポーネントにあることを簡単に理解できます (アルゴリズムの視覚化)。