1

试图找到a 、 via中的所有循环。但是遇到了问题。directed graphDFS

问题

当2个节点之间有多个循环时，有时只能检测到最长的一个，较短的一个被跳过。

这是因为当访问一个节点时，我会跳过它，从而跳过较短的循环。但是，如果我不跳过访问过的节点，DFS 搜索将永远重复。

例子

图形：

1 -> [2, 4]
2 -> [3]
3 -> [4]
4 -> [1]

1和之间有 2 个循环4：

  • (A) 1 -> 2 -> 3 -> 4 -> 1
  • (B) 1 -> 4 -> 1

无法检测到循环B，如果先检测到A，因为4访问过会被跳过，并且永远不会回到1。

当前的想法

  • 一种可能的解决方案是从每个节点开始，即使它已经被访问过。但我想要一个更好的解决方案。
  • 计算并记住路径的哈希，仅当存在相同的哈希时才跳过？这需要一些记忆，对吧？并且，仍然有可能 2 条具有相同哈希的不同路径导致相同的节点，它不能完全解决问题。

任何想法？

4

1 回答 1

0

学分：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 开始的循环时已考虑过。

让我介绍一个可以帮助您完成任务的具体参考。这是约翰逊的算法。显然，这是完成任务的最快方式。

在第 3 页，它提到：

为了避免重复电路，当顶点 v 添加到以 s 开始的某个基本路径时，它会被阻塞。只要从 v 到 s 的每条路径在除 s 之外的顶点处与当前基本路径相交，它就会保持阻塞。此外，一个顶点不会成为构造基本路径的根顶点，除非它是至少一个基本电路中的最小顶点。

您也可以观看此 youtube 视频以了解更多信息。

我认为这个信息是可以接受的。

于 2020-11-03T05:38:16.290 回答