algorithm - 寻找不同类型的连接组件

Question

我想在有向图中将一个单连接组件定义为一个子图，其中对于每对节点 u 和 v 存在从 u 到 v 或从 v 到 u 的路径。它还应该具有不是另一个单连接组件的子图的属性。

我知道如何找到弱连接和强连接的组件。如何找到单连接组件？

一种非常低效的方法可能会从每个节点进行广度搜索，以查看可以从它到达哪些节点，并尝试以某种方式从这些节点集计算组件。

Answer 1

最大单连通子图（我拒绝称它们为“组件”，因为底层关系不是传递的）包含所有或不包含强连通组件。作为枚举最大单连通子图的第一步，然后，将每个 SCC 折叠到单个顶点（即，计算输入图的压缩）。

无环有向图的单连通子图具有以下性质：对于不同的节点 u 和 v，要么存在从 u 到 v 的路径，要么存在从 v 到 u 的路径，但不能同时存在。如果存在从 u 到 v 且 u != v 的路径，则写 u < v。由于 u < v 或 v < u 但不是两者兼有，并且 u < v 和 v < w 意味着 u < w，因此关系 < 是严格的总订单。通过对子图中的顶点进行排序，我们发现它们位于一条路径上。当且仅当没有顶点可以插入时，这条路径是最大的，这意味着它开始于源（没有传入边），结束于宿（没有传出边），并且仅由出现在传递缩减中的边组成的无环有向图。

这是一种用于枚举有向图 G 的最大单连通子图的算法。

1. 找到 G 的强分量。收缩它们，产生凝聚 G'。
2. 计算 G' 的传递约简 G''。
3. 通过例如深度优先搜索枚举所有源-汇路径，然后用其在 G 中的强分量替换每个节点。

这是一个图族，其具有成倍增长的最大单连通子图。所有边缘都指向下方。

  *
 / \
*   *
 \ /
  *
 / \
*   *
 \ /
  *
 / \
  .
  .
  .
 \ /
  *
 / \
*   *
 \ /
  *

Answer 2

构造一个无向图 G，它具有与原始图相同的节点集，并且每对节点之间的边由原始图中任一方向的边连接。

通过广度优先搜索找到 G 的连通分量。遍历节点，但仅在不属于任何先前找到的组件的节点处开始新的搜索。见（https://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29#Algorithms）

这些组件中的每一个的节点也形成了原始有向图的单连通组件的节点。

==================================================== ===========

我现在明白了，每个节点都必须与无向图子集中的每个其他节点都有边对边，所以需要的是 G 中的一个集团，而不是 G 的一个连通子图。不幸的是，决策形式问题是NP完全的，函数形式是NP难的。

请参阅算法以获取查找集团的一些免费选项。