特定の頂点、たとえばV0が、グラフGの他のすべての頂点から
到達可能かどうかを確認したいと思います。グラフ内の各頂点をトラバースし、BFS / DFSを実行して、V0が到達可能かどうかを確認できます。
ただし、これは非常に非効率的なようです。
グラフでSCCアルゴリズムを実行し、v0がすべてのsccの一部である場合、v0はすべての頂点で到達可能であると安全に結論付けることができますか？SCCのコストはTarjanのO（V + E）のみであり、v0がsccの一部であるかどうかを確認すると、線形時間もかかるため、これは素晴らしいことです。
SCCは頂点に到達できることを意味するため、これは理にかなっていると思います。このロジックの確認はありますか？
またはこれへの効率的なアプローチ？
V0はSCCに属していない可能性がありますが、他のすべての頂点から到達可能です。たとえば、dダイアグラム上の頂点は他のすべての頂点から到達可能ですが、重要なSCCには頂点が含まれているだけでa、b頂点cは含まれていませんd。
V0が他のすべての頂点から到達可能かどうかを確認するには、すべてのエッジの方向を逆にして（線形時間で）、V0から開始してBFS / DFSを使用して、他のすべての頂点がV0から到達可能かどうかを確認します（線形時間でも） 。
他のすべての頂点に到達できる頂点をビスタ頂点と呼びましょう。グラフにビスタ頂点がある場合、ソース SCC は 1 つだけである必要があり (2 つのソース SCC は互いに到達できないため)、これにはビスタ頂点が含まれている必要があります (他の SCC にある場合、ビスタからのパスはありません)。ソース SCC への頂点)。さらに、この場合、ソース SCC のすべての頂点がビスタ頂点になります。次に、アルゴリズムは、任意のノードから開始する DFS に対して単純に行われ、終了時間が最も長い頂点をマークします。これはソース SCC にある必要があります。この頂点から再び DFS を実行して、すべてのノードに到達できるかどうかを確認します。アルゴリズムは SCC と DFS への分解を使用するだけなので、実行時間は線形です。このアルゴリズムは正しいです。ソース SCC が 1 つしかない場合にのみ、ビスタ頂点が存在することに注意してください。ソース SCC 内の頂点は、同じ SCC 内の他の頂点によってのみ到達可能であるため、頂点は 2 つの異なるソース SCC 内の頂点に到達できません。さらに、ソース SCC が 1 つしかない場合、その SCC 内の頂点はすべて相互に到達可能であるため、ビスタ頂点です。特定の SCC で開始する DFS は、到達可能なすべての SCC が探索されるまで終了しないことに注意してください。これは、終了する最後のノードが、他のどの SCC からも到達できない SCC、つまりソース SCC にあることを意味します。したがって、アルゴリズムの最初の部分で、ソース SCC のノードを見つけます。DFS を実行することで、それがビスタ頂点であるかどうかを正しく判断し、ビスタ頂点でない場合は、グラフに何も存在しないことがわかります。さらに、ソース SCC が 1 つしかない場合、その SCC 内の頂点はすべて相互に到達可能であるため、ビスタ頂点です。特定の SCC で開始する DFS は、到達可能なすべての SCC が探索されるまで終了しないことに注意してください。これは、終了する最後のノードが、他のどの SCC からも到達できない SCC、つまりソース SCC にあることを意味します。したがって、アルゴリズムの最初の部分で、ソース SCC のノードを見つけます。DFS を実行することで、それがビスタ頂点であるかどうかを正しく判断し、ビスタ頂点でない場合は、グラフに何も存在しないことがわかります。さらに、ソース SCC が 1 つしかない場合、その SCC 内の頂点はすべて相互に到達可能であるため、ビスタ頂点です。特定の SCC で開始する DFS は、到達可能なすべての SCC が探索されるまで終了しないことに注意してください。これは、終了する最後のノードが、他のどの SCC からも到達できない SCC、つまりソース SCC にあることを意味します。したがって、アルゴリズムの最初の部分で、ソース SCC のノードを見つけます。DFS を実行することで、それがビスタ頂点であるかどうかを正しく判断し、ビスタ頂点でない場合は、グラフに何も存在しないことがわかります。これは、終了する最後のノードが、他のどの SCC からも到達できない SCC、つまりソース SCC にあることを意味します。したがって、アルゴリズムの最初の部分で、ソース SCC のノードを見つけます。DFS を実行することで、それがビスタ頂点であるかどうかを正しく判断し、ビスタ頂点でない場合は、グラフに何も存在しないことがわかります。これは、終了する最後のノードが、他のどの SCC からも到達できない SCC、つまりソース SCC にあることを意味します。したがって、アルゴリズムの最初の部分で、ソース SCC のノードを見つけます。DFS を実行することで、それがビスタ頂点であるかどうかを正しく判断し、ビスタ頂点でない場合は、グラフに何も存在しないことがわかります。