algorithm - 同じタイプのノードの最長のチェーンを見つける

Question

さまざまなタイプの相互接続されたノードのツリー構造があります。各ノードは、接続されているノードを追跡します。この構造では、同じタイプのノードの接続されていない最長のチェーンまたはパスを見つける必要があります。

グラフと幅/深さ優先探索を読みましたが、これらは必要な結果を完全には得られません。（チェーンは見つかりますが、起点ノードと終点ノードの間のすべての行き止まりの分岐も含まれます）

この目的のための既存のアルゴリズムはありますか？

Answer 1

「チェーン」が接続されたコンポーネントを意味する場合、

グラフにエッジ E と頂点 V があるとします。

エッジを反復処理し、異なるタイプのノードを接続するすべてのエッジを削除します。これが O(|E|) です。

深さ優先または幅優先を使用して、連結要素を見つけます。これは O(|E|+|V|) です。

最大の接続コンポーネントは、同じタイプのノードの最長チェーンになります。

チェーンが単純なサイクル(開始、同じノードで停止、ノードを再訪しない) を意味する場合、これは NP 完全です。接続されたコンポーネントが小さい場合でも、実現可能であるはずです。

チェーンで単純なパスを意味する場合、これは NP-Hard です。