51

请注意,图表示为邻接列表。

我听说过在图中找到循环的两种方法:

  1. 保留一个布尔值数组以跟踪您之前是否访问过某个节点。如果你用完了新的节点(没有碰到你已经去过的节点),那么只需回溯并尝试不同的分支。

  2. 来自 Cormen 的 CLRS 或 Skiena 的那个:对于无向图中的深度优先搜索,有两种类型的边,树和后边。当且仅当存在后边时,该图才具有循环。

有人可以解释一下图的后边缘是什么以及上述两种方法之间的区别是什么。

谢谢。

更新: 这是在这两种情况下检测周期的代码。Graph 是一个简单的类,为简单起见,将所有图节点表示为唯一数字,每个节点都有其相邻的相邻节点(g.getAdjacentNodes(int)):

public class Graph {

  private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};

  public int[] getAdjacentNodes(int v) {
    return nodes[v];
  }

  // number of vertices in a graph
  public int vSize() {
    return nodes.length;
  }

}

用于检测无向图中的循环的 Java 代码:

    public class DFSCycle {

    private boolean marked[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    // s - starting node
    public DFSCycle(Graph g, int s) {
        this.g = g;
        this.s = s;
        marked = new boolean[g.vSize()];
        findCycle(g,s,s);
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public void findCycle(Graph g, int v, int u) {

        marked[v] = true;

        for (int w : g.getAdjacentNodes(v)) {
            if(!marked[w]) {
                marked[w] = true;
                findCycle(g,w,v);
            } else if (v != u) {
                hasCycle = true;
                return;
            }
        }

    }  
}

用于检测有向图中的循环的 Java 代码:

public class DFSDirectedCycle {

    private boolean marked[];
    private boolean onStack[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    public DFSDirectedCycle(Graph g, int s) {
        this.s = s
        this.g = g;
        marked = new boolean[g.vSize()];
        onStack = new boolean[g.vSize()];
        findCycle(g,s);
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public void findCycle(Graph g, int v) {

        marked[v] = true;
        onStack[v] = true;

        for (int w : g.adjacentNodes(v)) {
            if(!marked[w]) {
                findCycle(g,w);
            } else if (onStack[w]) {
                hasCycle = true;
                return;
            }
        }

        onStack[v] = false;
    }
}
4

4 回答 4

66

回答我的问题:

当且仅当存在后边时,该图才具有循环。后边是从节点到自身(自循环)或其在由 DFS 生成的树中的祖先之一形成循环的边。

上述两种方法实际上是相同的。但是,这种方法只能应用于无向图

该算法不适用于有向图的原因是,在有向图中,到同一顶点的 2 条不同路径不会形成循环。例如:A-->B, B-->C, A-->C - 不要循环,而在无向循环中: A--B, B--C, C--A 会。

在无向图中找到一个循环

当且仅当深度优先搜索 (DFS) 找到指向已访问顶点的边(后边)时,无向图才具有循环。

在有向图中找到一个循环

除了访问的顶点之外,我们还需要跟踪当前在 DFS 遍历函数的递归堆栈中的顶点。如果我们到达一个已经在递归堆栈中的顶点,那么树中有一个循环。

更新: 工作代码在上面的问题部分。

于 2013-10-01T11:34:48.893 回答
10

为了完成,可以使用 DFS(来自wikipedia)在有向图中找到循环:

 L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 
function visit(node n)
    if n has a temporary mark then stop (not a DAG)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L
于 2014-12-18T17:45:30.340 回答
1

这是我基于 DFS 用 C 语言编写的代码,用于确定给定的无向图是否连通/循环。最后有一些示例输出。希望它会有所帮助:)

#include<stdio.h>
#include<stdlib.h>

/****Global Variables****/
int A[20][20],visited[20],count=0,n;
int seq[20],connected=1,acyclic=1;

/****DFS Function Declaration****/
void DFS();

/****DFSearch Function Declaration****/
void DFSearch(int cur);

/****Main Function****/
int main() 
   {    
    int i,j;

    printf("\nEnter no of Vertices: ");
    scanf("%d",&n);

    printf("\nEnter the Adjacency Matrix(1/0):\n");
    for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
        scanf("%d",&A[i][j]);

    printf("\nThe Depth First Search Traversal:\n");

    DFS();

    for(i=1;i<=n;i++)
        printf("%c,%d\t",'a'+seq[i]-1,i);

    if(connected && acyclic)    printf("\n\nIt is a Connected, Acyclic Graph!");
    if(!connected && acyclic)   printf("\n\nIt is a Not-Connected, Acyclic Graph!");
    if(connected && !acyclic)   printf("\n\nGraph is a Connected, Cyclic Graph!");
    if(!connected && !acyclic)  printf("\n\nIt is a Not-Connected, Cyclic Graph!");

    printf("\n\n");
    return 0;
   }

/****DFS Function Definition****/
void DFS()
    { 
    int i;
    for(i=1;i<=n;i++)
        if(!visited[i])
          {
        if(i>1) connected=0;
        DFSearch(i);    
              } 
    }

/****DFSearch Function Definition****/
void DFSearch(int cur) 
    {
    int i,j;
    visited[cur]=++count;

        seq[count]=cur; 
        for(i=1;i<count-1;i++)
                if(A[cur][seq[i]]) 
                   acyclic=0;

    for(i=1;i<=n;i++)
        if(A[cur][i] && !visited[i])
           DFSearch(i);

    }

样本输出:

majid@majid-K53SC:~/Desktop$ gcc BFS.c

majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 10

Enter the Adjacency Matrix(1/0):

0 0 1 1 1 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 1 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 1 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 1 0 0 0 

The Depdth First Search Traversal:
a,1 c,2 d,3 f,4 b,5 e,6 g,7 h,8 i,9 j,10    

It is a Not-Connected, Cyclic Graph!


majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 4

Enter the Adjacency Matrix(1/0):
0 0 1 1
0 0 1 0
1 1 0 0
0 0 0 1

The Depth First Search Traversal:
a,1 c,2 b,3 d,4 

It is a Connected, Acyclic Graph!


majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 5

Enter the Adjacency Matrix(1/0):
0 0 0 1 0
0 0 0 1 0
0 0 0 0 1
1 1 0 0 0 
0 0 1 0 0

The Depth First Search Traversal:
a,1 d,2 b,3 c,4 e,5 

It is a Not-Connected, Acyclic Graph!

*/
于 2015-05-17T00:42:37.293 回答
1

我认为上面的代码仅适用于连接的有向图,因为我们仅从源节点启动 dfs,因为如果有向图未连接,则其他组件中可能存在一个可能被忽视的循环!

于 2019-01-15T07:15:44.533 回答