algorithm - 寻找最长的同类型节点链

Question

我有各种类型的互连节点的树结构。每个节点都跟踪它连接到的节点。在这个结构中，我需要找到最长的未连接链或相同类型节点的路径。

我已经阅读了图表和广度/深度优先搜索，但这些并不能完全产生我需要的结果。（他们会找到一条链，但也包括起点和终点节点之间的所有死胡同）

是否有用于此目的的现有算法？

Answer 1

如果“链”是指连接的组件，那么

假设你的图有边 E 和顶点 V。

遍历边，删除所有连接不同类型节点的边。这是 O(|E|)。

使用深度优先或广度优先查找连接的组件。这是 O(|E|+|V|)。

最大的连接组件将是最长的同类型节点链。

如果按链表示简单循环（在同一节点开始，停止，不重新访问任何节点），那么这是 NP 完整的。如果连接的组件很小，它应该是可行的。

如果链式是指简单路径，那么这就是 NP-Hard。