现在性能不重要,我只是想理解算法。我已经阅读了深度优先搜索算法的定义,但我不完全理解该如何操作。
我没有任何完成的代码片段可以提供在这里,因为我不确定如何:
- 存储结果(以及A->B->C->我们还应该存储A->B和A->B->C); - 表示图(有向图?元组列表?); - 使用多少递归(处理每个相邻的顶点?)。
如何在Erlang中找到有向循环图中给定源顶点的所有可能路径?
更新:根据迄今为止的答案,我必须重新定义图的定义:它是一个非无环图。我知道如果我的递归函数遇到循环,它就是一个无限循环。为了避免这种情况,我可以检查当前顶点是否在结果路径列表中 - 如果是,则停止遍历并返回路径。
更新2:感谢思考启发性的评论!是的,我需要找到所有从一个源顶点到其他所有顶点的简单路径,这些路径都没有循环。
在这样的图中:
[图片]
以源顶点A为例,算法应该找到以下路径:
- A,B - A,B,C - A,B,C,D - A,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个顶点,每个顶点有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).
有什么方法可以在合理的时间内运行它?