Я хотел бы реализовать функцию, которая находит все возможные пути ко всем возможным вершинам из исходной вершины V в ориентированном циклическом графе G.
Производительность теперь не имеет значения, я просто хотел быпонять алгоритм.Я прочитал определение алгоритма поиска в глубину, но у меня нет полного понимания того, что делать.
У меня нет готового фрагмента кода, чтобы предоставить здесь, потому что я неубедитесь, что:
- сохраните результаты (наряду с A-> B-> C-> мы также должны хранить A-> B и A-> B-> C);
- представляют график (digraph? Список кортежей?);
- сколько рекурсий использовать (работать с каждой смежной вершиной?).
Как найтивсе возможные пути образуют одну заданную исходную вершину в ориентированном циклическом графе в Erlang?
UPD: Основываясь на ответах, которые я до сих пор должен был переопределить, определение графа: это неациклический граф.Я знаю, что если моя рекурсивная функция попадает в цикл, это неопределенный цикл.Чтобы избежать этого, я могу просто проверить, есть ли текущая вершина в списке полученного пути - если да, я прекращаю обход и возвращаю путь.
UPD2: Спасибодля размышлений, вызывающих комментарии!Да, мне нужно найти все простые пути, у которых нет петель из одной исходной вершины во все остальные.
В графе, подобном этому:
с исходной вершиной 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) и никогда не идет по второму.path.
В любом случае это будет единственный путь - например, когда обычные возвратные дорожки DFS из (A, B, C, D) возвращаются к A и проверяет, является ли D (вторым соседом)а) посещается.А поскольку обычная DFS поддерживает глобальное состояние для каждой вершины, D будет иметь «посещенное» состояние.
Итак, мы должны ввести рекурсивно-зависимое состояние - если мы возвращаемся из (A, B, C,D) до A у нас должно быть (A, B, C, D) в списке результатов, и мы должны иметь D, помеченный как не посещенный, как в самом начале алгоритма.
Я пыталсяоптимизировать решение для хвостовой рекурсии, но время выполнения алгоритма неосуществимо - требуется около 4 секунд, чтобы пройти крошечный граф из 16 вершин с 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).
Любойидеи запустить это в приемлемое время?