查找选定节点的有向未加权图中的所有路径

Question

围绕这个主题有几个类似的问题，但我找不到符合我要求的问题。我正在研究一个食物网络程序（在 Javascript 中），并且有兴趣找到涉及选定物种（节点）的所有可能的食物链（路径）。换句话说，当有人在图中选择一个物种时，我想列出或突出显示涉及所选物种的每个单独的食物链。有关我正在处理的图表类型的示例，请参阅 EOL Food Web。

我希望这不会太复杂，因为边缘没有加权（没有价值）但确实有方向。我不需要最短或最长的路径 - 只需要涉及相关物种的所有可能变化。

我在想一个聪明的解决方案可能涉及首先从所选节点找到所有 "down"（朝向猎物）路径，然后对 "up"（朝向捕食者）路径执行相同的操作。然后将所有可能组合的起伏连接起来。但这可能不是很优雅。

非常感谢您的想法！

Answer 1

您的解决方案大致正确。

递归遍历图"downwards"记录所有路径
递归遍历图"upwards"记录所有路径
生成前两组的所有路径组合。

这假设该图没有循环（即没有生物以自身或任何捕食者或捕食者的捕食者等为食）

下面是一些遍历的伪代码。使用递归方法从感兴趣的节点开始：

paths := []
for all children
    extendPath(paths, child)


function extendPath(NodeList[] paths, Node node)    
    for path in paths
        path.add(node)

    for child in node.children
        extendPath(paths, child)

查找选定节点的有向未加权图中的所有路径

Find all paths in a directed, unweighted graph for a selected node

javascript

graph

nodes