algorithm - 在有向图上查找关联的源和目标

Question

背景:我有一组节点，代表产品在流程中移动时的交集。这些节点连接在一起形成有向图。有几个独立的图，因为产品并不总是相交。

产品总是从一个没有父节点的初始源节点开始。它最终将在最终目的地节点结束，一个没有 child 的节点。一个初始源可能有一个或多个最终目的地，一个最终目的地可能有一个或多个初始源。

我们能够编制一份所需初始来源的列表，以遵循用户给出的一组标准。这些来源可能但不一定属于同一个图。

目标:鉴于此初始来源列表，我需要能够确定哪些初始来源对应于哪些最终目的地。这些来源和目的地必须按图表分组，不得重复。换句话说:

1. 将每个节点与其唯一的图相关联。
2. 确定属于每个图的初始来源。
3. 确定属于每个图的最终目的地。

示例:如果我的初始来源列表是 1、2、3、4、5、6、7 和 8，我将得到以下结果(我的未知目的地是 A， C、D、E、G、K、L):

1,4,5,6 -> A,G,K
2 -> C
3 -> D,E
7,8 -> L

问题:什么是执行此任务的有效(并且希望是最有效的)算法？

当前解决方案，仅供引用:

For each initial source:
    If we have not visited the initial source yet
        Mark as belonging to a new graph

        Add childrens to a list of nodes to visit.        

        For each node to visit:
            If we have not visited this node yet:
                Mark as belonging to current graph

                If there are no children
                    add to list of final destinations
                End if

                add all parents and all children to a list of nodes to visit
            End if
        Do next node
    End if
Do next source

显然，由于我们要访问每个节点的所有子节点和所有父节点，因此我们将对之前已经见过的节点进行大量访问，因此会产生一些额外的开销。

Answer 1

您所描述的算法是一个Depth First Search .这种类型的问题，即遵循无环有向图的问题，可能由 Breadth First Search 更好地处理。 .即使图不是非循环的，这仍然可能是更好的方法。