如何处理有向图中强连通分量的节点？
How to process nodes of strongly connected components in a directed graph?
我是图形算法编程领域的初学者。我正在为一个关于强连接组件的有趣问题而苦苦挣扎，非常感谢任何与此相关的帮助。
在我的应用程序中，目标是尽可能在多个线程上执行任务。这些任务在有向图中表示为节点，并且任务可能具有循环依赖性。通过找到强连接的组件然后执行预定义的规则来删除边缘来打破循环依赖性。这样，强连接组件中的所有任务将最终串行执行。
现在考虑一个示例，其中任务 1,2,...8 具有以下依赖模式。 {1 -> 2、2 -> 3、3 -> 1、3 -> 4、4 -> 5、5 -> 6、6 -> 4、7 -> 8}。使用强连通分量和预定义规则来打破循环依赖，我们得到三组节点，即 A={1 -> 2 -> 3}、B={4 -> 5 -> 6} 和 C={7 - > 8}，但由于 A 和 B 由一条边连接，因此它们不能并行执行。
我想知道是否有任何算法或一组算法可用于获取节点集，以便我可以将 A 和 B 顺序执行，而 C 可以与 A 或 B 并行执行. 根据我的理解，拓扑排序可能会有帮助，但它仅用于非循环图。非常感谢任何建议或帮助。谢谢。
您用节点 A、B、C 等描述的商图始终是非循环的：如果它有一个循环，例如涉及 A 和 B，则 A 中的所有任务都可以从 B 中的所有任务访问，反之亦然反之亦然，所以 A 和 B 是同一个 SCC。
所以是的，您可以对该图进行拓扑排序。
我是图形算法编程领域的初学者。我正在为一个关于强连接组件的有趣问题而苦苦挣扎，非常感谢任何与此相关的帮助。
在我的应用程序中，目标是尽可能在多个线程上执行任务。这些任务在有向图中表示为节点，并且任务可能具有循环依赖性。通过找到强连接的组件然后执行预定义的规则来删除边缘来打破循环依赖性。这样，强连接组件中的所有任务将最终串行执行。
现在考虑一个示例，其中任务 1,2,...8 具有以下依赖模式。 {1 -> 2、2 -> 3、3 -> 1、3 -> 4、4 -> 5、5 -> 6、6 -> 4、7 -> 8}。使用强连通分量和预定义规则来打破循环依赖，我们得到三组节点，即 A={1 -> 2 -> 3}、B={4 -> 5 -> 6} 和 C={7 - > 8}，但由于 A 和 B 由一条边连接，因此它们不能并行执行。
我想知道是否有任何算法或一组算法可用于获取节点集，以便我可以将 A 和 B 顺序执行，而 C 可以与 A 或 B 并行执行. 根据我的理解，拓扑排序可能会有帮助，但它仅用于非循环图。非常感谢任何建议或帮助。谢谢。
您用节点 A、B、C 等描述的商图始终是非循环的：如果它有一个循环，例如涉及 A 和 B，则 A 中的所有任务都可以从 B 中的所有任务访问，反之亦然反之亦然，所以 A 和 B 是同一个 SCC。 所以是的，您可以对该图进行拓扑排序。