有向グラフの各頂点に、外向きのパス (同じ頂点を指すことができる) が正確に 4 つあるという特定の問題があります。
最初は開始頂点しかなく、DFS を使用してすべての頂点とエッジを検出/列挙します。
その後、Tarjan のアルゴのようなものを使用して、グラフを強く接続されたコンポーネントに分割できます。
私の質問は、グラフを発見してからアルゴリズムを適用するよりも効率的な方法があるかどうかです。たとえば、2 つの部分を組み合わせてより効率的にする方法はありますか?
有向グラフの各頂点に、外向きのパス (同じ頂点を指すことができる) が正確に 4 つあるという特定の問題があります。
最初は開始頂点しかなく、DFS を使用してすべての頂点とエッジを検出/列挙します。
その後、Tarjan のアルゴのようなものを使用して、グラフを強く接続されたコンポーネントに分割できます。
私の質問は、グラフを発見してからアルゴリズムを適用するよりも効率的な方法があるかどうかです。たとえば、2 つの部分を組み合わせてより効率的にする方法はありますか?