我想实现一个函数，该函数在有向循环图 G 中找到从源顶点 V 到所有可能顶点的所有可能路径。
现在性能无关紧要，我只想了解算法。我已经阅读了深度优先搜索算法的定义，但我没有完全理解要做什么。
我没有任何完整的代码在这里提供，因为我不知道如何:
如何在 Erlang 的有向循环图中找到来自一个给定源顶点的所有可能路径？
UPD:基于到目前为止的答案，我必须重新定义图定义:它是一个非循环图。我知道如果我的递归函数遇到一个循环，它就是一个无限循环。为了避免这种情况，我可以只检查当前顶点是否在结果路径的列表中——如果是，我停止遍历并返回路径。
UPD2:感谢发人深省的评论!是的，我需要找到所有没有从一个源顶点到所有其他源顶点的循环的简单路径。
在这样的图表中:
对于源顶点 A，算法应该找到以下路径:
下面的代码完成了这项工作，但它不能用于具有超过 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 个顶点且每个顶点有 3 个边的小图大约需要 4 秒:
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).
有什么想法可以在可接受的时间内运行它吗？
最佳答案
我不明白问题。如果我有图 G = (V, E) = ({A,B}, {(A,B),(B,A)})，从 A 到 B {[A,B], [ A,B,A,B], [A,B,A,B,A,B], ...}。如何找到循环图中任何顶点的所有可能路径？
编辑:
您是否尝试过计算或猜测某些图形的可能路径的增长？如果你有全连接图，你会得到
您确定要查找所有节点的所有路径吗？这意味着如果您在一秒钟内计算出一百万条路径，那么计算到具有 20 个节点的全连接图中所有节点的所有路径将需要 10750 年的时间。这是您任务的上限，所以我认为您不想这样做。我想你想要别的东西。
关于graph - 从 Erlang 中的有向循环图中的一个顶点找到所有可能的路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7834702/