无向图中的循环

这是我基于深度优先搜索算法写的C代码，用于判断给定图是否连通/有环。最后也附带了一些样例输出。希望对你有所帮助 :)

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

/****Global Variables****/
int A[20][20],visited[20],v=0,count=0,n;
int seq[20],s=0,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!

*/

我认为正确使用DFS还取决于你如何在代码中表示图形。例如，假设您正在使用相邻列表来跟踪相邻节点，并且您的图形具有2个顶点和仅一个边缘：V = {1,2}和E = {(1,2)}。在这种情况下，从顶点1开始，DFS将将其标记为VISITED，并将2放入队列中。之后，它将弹出顶点2，并且由于1与2相邻，而1已经被访问过，DFS将得出结论存在一个循环（这是错误的）。 换句话说，在无向图中，(1,2)和(2,1)是相同的边缘，您应该以一种方式编码，使DFS不将它们视为不同的边缘。为每个访问的节点保留父节点将有助于处理此情况。

正如其他人所提到的... 深度优先搜索可以解决它。 一般来说，深度优先搜索需要O(V + E)的时间复杂度，但在这种情况下，您知道图最多有O(V)条边。因此，您可以简单地运行DFS，并且一旦看到新边增加计数器。当计数器达到V时，您不必继续，因为图肯定有一个循环。 显然，这需要O(v)的时间复杂度。

这里是一个简单的C++实现算法，用于检查图中是否存在环，时间复杂度为O(n)（n是图中顶点的数量）。我没有展示图数据结构的实现（为了保持答案简短）。该算法期望Graph类具有公共方法vector<int> getAdj(int v)，返回与v相邻的顶点和int getV()，返回总顶点数。此外，该算法假定图的顶点从0到n-1编号。

class CheckCycleUndirectedGraph
{
private:
    bool cyclic;
    vector<bool> visited;

    void depthFirstSearch(const Graph& g, int v, int u) {
        visited[v] = true;
        for (auto w : g.getAdj(v)) {
            if (!visited[w]) {
                depthFirstSearch(g, w, v);
            }
            else if (w != u) {
                cyclic = true;
                return;
            }
        }
    }

public:
    CheckCycleUndirectedGraph(const Graph& g) : cyclic(false) {
        visited = vector<bool>(g.getV(), false);
        for (int v = 0; v < g.getV(); v++) {
            if (!visited[v]){
                depthFirstSearch(g, v, v);
                if(cyclic)
                  break;
            }
        }
    }

    bool containsCycle() const {
        return cyclic;
    }
};

请注意，图可能由多个不相连的组件组成，并且组件内部可能存在循环。所示算法也可以检测这种图中的循环。

最近我开始学习图形。我用Java写了一段代码，可以确定一个图是否有循环。我使用DFT在图中查找循环。我使用堆栈来遍历图，而不是使用递归。

使用堆栈的DFT的高级步骤如下：

1. 访问一个节点
2. 如果该节点不在已访问列表中，则将其添加到列表中并将其推送到堆栈顶部
3. 将堆栈顶部的节点标记为当前节点。
4. 对于当前节点的每个相邻节点重复上述步骤
5. 如果所有节点都已访问，则从堆栈中弹出当前节点

我从图的每个节点执行了DFT，在遍历过程中，如果我遇到了一个之前访问过的顶点，我检查该顶点的堆栈深度是否大于1。我还检查节点是否有自身边缘以及节点之间是否存在多个边缘。我最初编写的堆栈版本不太优雅。我阅读了使用递归的伪代码，它非常简洁。这是一个Java实现。LinkedList数组表示一个图形，其中每个节点及其相邻顶点分别由数组的索引和每个项目表示。

class GFG {
Boolean isCyclic(int V, LinkedList<Integer>[] alist) {
    List<Integer> visited = new ArrayList<Integer>();
    for (int i = 0; i < V; i++) {
        if (!visited.contains(i)) {
            if (isCyclic(i, alist, visited, -1))
                return true;
        }
    }
    return false;
}

Boolean isCyclic(int vertex, LinkedList<Integer>[] alist, List<Integer> visited, int parent) {
    visited.add(vertex);
    for (Iterator<Integer> iterator = alist[vertex].iterator(); iterator.hasNext();) {
        int element = iterator.next();
        if (!visited.contains(element)) {
            if (isCyclic(element, alist, visited, vertex))
                return true;
        } else if (element != parent)
            return true;
    }
    return false;
}

}

你可以使用 boost图形库 和 循环依赖。它具有使用 back_edge 函数查找循环的解决方案。

一个没有环的无向图，其边数 |E| 必须小于 |V|-1。

public boolean hasCycle(Graph g) {

   int totalEdges = 0;
   for(Vertex v : g.getVertices()) {
     totalEdges += v.getNeighbors().size();
   }
   return totalEdges/2 > g.getVertices().size - 1;

}