尝试通过DFS查找directed graph中的所有循环。但遇到了问题。
问题
当两个节点之间有多个周期时，有时只能检测到最长的一个，跳过较短的一个。
这是因为当访问一个节点时，我会跳过它，从而跳过较短的周期。但是，如果我不跳过已访问的节点，DFS搜索将永远重复。
示例
图表：
1 -> [2, 4]
2 -> [3]
3 -> [4]
4 -> [1]
1和4之间有2个循环：
- (A(1->2->3->4->1
- (B(1->4->1
如果首先检测到A，则无法检测到循环B，因为4将由于访问而被跳过，并且它永远不会返回到1。
当前想法
- 一种可能的解决方案是从每个节点开始，即使它已经访问过。但我想要一个更好的解决方案
- 计算&还记得路径的散列吗，只有当存在相同的散列时才跳过？那需要一些记忆，对吧？而且，仍然有可能有两个不同的路径具有相同的哈希导致相同的节点，这不能完全解决问题
知道吗？
学分：https://www.hackerearth.com/practice/notes/finding-all-elementry-cycles-in-a-directed-graph/
integer list array A(n);logical array marked(n);integer stack current_stack ;integer stack marked_stack;/* A(n) is the array of list wich is adjacency list representation*/
integer procedure intialize(); /*initialize the values*/
begin;
for i in n do
marked(i):=false
integer procedure print_cycles();
begin
for i in current_stack do
print i ;
logical procedure backtrack(k) do
begin
logical flag=false;
current_stack->push(k);
marked_stack->push(k);
marked(n):=true;
for i in A(k) do
if i < s; /* To find only disticnt cycles in topological manner*/
delete A(i);
if i==s; /Cycle found */
print_cycles()
if marked(i):= false;
backtrack(n); /*continue dfs*/
if flag :=true;
for i in marked_stack do /*unmark the elements that have been visited in any of the cycles starting from s*/
marked(i):=false;
current_stack->pop(k);
backtrack:=flag
end backtrack(k)
begin
integer procedure backtrack_Util();
begin
for s in n do
backtrack(s);
while marked_stack(s)->empty do
for i in marked_stack do
marked(i):=false
end backtrack_Util()
我们希望找到不同的循环。因此，我们需要按某种顺序访问顶点。按照这个顺序，我们需要找到从该顶点开始的循环，并且循环不应包含排序中起始顶点之前的任何顶点。如何获得订单？上述评论之一中的单词topological manner与topological sort不明确，但事实并非如此。我认为我们可以选择一个简单的排序，比如0，1，2，。。，v.假设我们希望找到一个从2开始的循环。为了避免发现重复的循环，我们将不使用顶点0和1。如果存在由从2到1或从2到0的边组成的任何循环，则在查找从0或1开始的循环时已经考虑了该循环。
让我介绍一个具体的参考资料，它将帮助您完成任务。这是Johnson的算法。显然，这是完成任务最快的方法。
在第3页，它提到：
为了避免重复电路，添加顶点v时会将其阻塞到s开始的一些基本路径从v到s的每条路径在不是s的顶点。此外，顶点不会变成根构造初等路径的顶点，除非它是最小顶点在至少一个基本电路中。
您也可以观看此youtube视频以获得更多了解。
我认为这些信息是可以接受的。