在Erlang中查找有向循环图中一个顶点的所有可能路径

Question

我想实现一个函数,该函数在有向循环图G中找到来自源顶点V的所有可能顶点的所有可能路径.

性能现在没关系,我只是想了解算法.我已经阅读了深度优先搜索算法的定义,但我并不完全理解该怎么做.

我没有在这里提供任何完整的代码,因为我不知道如何:

• 存储结果(连同A-> B-> C->我们还应该存储A-> B和A-> B-> C);
• 代表图(有向图？元组列表？);
• 要使用多少递归(处理每个相邻的顶点？).

如何在Erlang中的有向循环图中找到形成一个给定源顶点的所有可能路径？

UPD:基于到目前为止的答案,我必须重新定义图形定义:它是一个非非循环图形.我知道如果我的递归函数遇到一个循环,它就是一个无限循环.为了避免这种情况,我可以检查当前顶点是否在结果路径的列表中 - 如果是,我停止遍历并返回路径.

---

UPD2:感谢发人深省的评论!是的,我需要找到所有简单路径,这些路径没有从一个源顶点到所有其他源的循环.

在这样的图表中:

使用源顶点A算法应找到以下路径:

• A,B
• A,B,C
• A B C D
• 广告
• A,d,C
• A,d,C,B

下面的代码完成了这项工作,但是对于具有更多20个顶点的图形它是不可用的(我猜它是递归错误的东西 - 占用太多内存,永远不会结束):

dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
            dfs(Neighbours,[Source],[],Graph,Source),
ok.


dfs([],Paths,Result,_Graph,Source) ->
    ?DBG("There are no more neighbours left for vertex ~w~n", [Source]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source) ->
    ?DBG("///The neighbour to check is ~w, other neighbours are: ~w~n",[Neighbour,Other_neighbours]),
    ?DBG("***Current result: ~w~n",[Result]),
    New_result = relax_neighbours(Neighbour,Paths,Result,Graph,Source),

        dfs(Other_neighbours,Paths,New_result,Graph,Source).


relax_neighbours(Neighbour,Paths,Result,Graph,Source) ->
     case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("Found an unvisited neighbour ~w, path is: ~w~n",[Neighbour,Paths]),
            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("The neighbours of the unvisited vertex ~w are ~w, path is:
                ~w~n",[Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,[Neighbour|Paths],Result,Graph,Source);
            true ->
                [Paths|Result]

        end.

---

UPD3:

问题是常规的深度优先搜索算法将首先进入路径之一:(A,B,C,D)或(A,D,C,B)并且永远不会进入第二条路径.

在任何一种情况下,它都是唯一的路径 - 例如,当常规DFS从(A,B,C,D)回溯时,它返回到A并检查是否访问了D(A的第二个邻居).由于常规DFS为每个顶点维护一个全局状态,因此D将具有"已访问"状态.

所以,我们必须引入一个依赖于递归的状态 - 如果我们从(A,B,C,D)回溯到A,我们应该在结果列表中有(A,B,C,D),我们应该在算法的最开始,将D标记为未访问.

我试图优化尾递归的解决方案,但算法的运行时间仍然不可行 - 遍历16个顶点的微小图形需要大约4秒,每个顶点有3个边缘:

dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
    Result = ets:new(resulting_paths, [bag]),
Root = Source,
            dfs(Neighbours,[Source],Result,Graph,Source,[],Root).


dfs([],Paths,Result,_Graph,Source,_,_) ->
    ?DBG("There are no more neighbours left for vertex ~w, paths are ~w, result is ~w~n", [Source,Paths,Result]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source,Recursion_list,Root) ->
    ?DBG("~w *Current source is ~w~n",[Recursion_list,Source]),
    ?DBG("~w Checking neighbour _~w_ of _~w_, other neighbours are: ~w~n",[Recursion_list,Neighbour,Source,Other_neighbours]),



?    DBG("~w Ready to check for visited: ~w~n",[Recursion_list,Neighbour]),

 case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("~w Found an unvisited neighbour ~w, path is: ~w~n",[Recursion_list,Neighbour,Paths]),
New_paths = [Neighbour|Paths],
?DBG("~w Added neighbour to paths: ~w~n",[Recursion_list,New_paths]),
ets:insert(Result,{Root,Paths}),

            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("~w The neighbours of the unvisited vertex ~w are ~w, path is: ~w, recursion:~n",[Recursion_list,Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,New_paths,Result,Graph,Neighbour,[[[]]|Recursion_list],Root);
            true -> 
            ?DBG("~w The neighbour ~w is: already visited, paths: ~w, backtracking to other neighbours:~n",[Recursion_list,Neighbour,Paths]),
ets:insert(Result,{Root,Paths})

end,

        dfs(Other_neighbours,Paths,Result,Graph,Source,Recursion_list,Root).

有什么想法在可接受的时间运行吗？

Answer 1

编辑： 好的，我现在明白了，您想要找到从有向图中的顶点开始的所有简单路径。因此，正如您所意识到的，带有回溯的深度优先搜索是合适的。总体思路是先去一个邻居，然后去另一个邻居（不是你去过的邻居），然后继续走，直到遇到死胡同。然后回溯到您所在的最后一个顶点并选择一个不同的邻居，等等。您需要正确处理繁琐的部分，但这应该不会太难。例如，在每一步中，您都需要将顶点标记为“已探索”或“未探索”，具体取决于您之前是否已经访问过它们。性能不应该是问题，正确实现的算法可能需要 O(n^2) 时间。所以我不知道你做错了什么，也许你拜访的邻居太多了？例如，也许您正在重新访问您已经访问过的邻居，并进行循环或其他操作。

我还没有真正读过你的程序，但是深度优先搜索的 Wiki 页面有一个简短的伪代码程序，你可以尝试用你的语言复制它。将图形存储为邻接列表以使其更容易。

编辑： 是的，抱歉，你是对的，标准的 DFS 搜索不会按原样工作，你需要稍微调整它，以便重新访问它之前访问过的顶点。因此，您可以访问除已存储在当前路径中的顶点之外的任何顶点。这当然意味着我的运行时间完全错误，你的算法的复杂性将达到顶峰。如果图的平均复杂度为 d+1，则大约有 d*d*d*...*d = d^n 条可能的路径。因此，即使每个顶点只有 3 个邻居，当顶点数量超过 20 个时，仍然有相当多的路径。实际上没有办法解决这个问题，因为如果你希望你的程序输出所有可能的路径，那么你实际上必须输出它们的所有 d^n 。

我很想知道您是否需要这个来完成特定任务，或者只是出于兴趣而尝试对此进行编程。如果是后者，您只需对小型、稀疏连接的图感到满意即可。