从无向图中的树根检测循环

Question

我想确定给定的图是否具有我想要的结构。我想要的结构是，如果给定图的树的根形成一个循环，则输出为真，否则为假。

这是一个示例图：它有3棵树，根1,5,4形成一个圈

这也是一个不应该通过的例子，因为它不包含根形成循环的树：

根据给定的顶点，我该如何决定应该搜索哪些树？

这是到目前为止的代码，打印给定图的邻接表。

#include <iostream>
#include <vector>
using namespace std; 
  
void addEdge(vector<int> vec[], int u, int v) 
{ 
    vec[u].push_back(v); 
} 

void printGraph(vector<int> vec[], int j) 
{
    cout << "Graph's adjacent list: \n";
    for (int v = 0; v < j; ++v) 
    { 
        if (vec[v].size() == 0) continue;
        cout << "Head(" << v << ")"; 
        for (auto x = vec[v].begin(); x != vec[v].end(); x++)
           cout << " -> " << *x; 
        cout << "\n" ; 
    } 
} 

int main() 
{ 
    int V = 10; 
    vector<int> vec[V];
    addEdge(vec, 6, 3); 
    addEdge(vec, 7, 1); 
    addEdge(vec, 8, 9); 
    addEdge(vec, 6, 4); 
    addEdge(vec, 5, 1); 
    addEdge(vec, 1, 9); 
    addEdge(vec, 2, 5); 
    addEdge(vec, 1, 4); 
    addEdge(vec, 5, 4); 
    printGraph(vec, V); 
    return 0; 
}

Answer 1

你的问题是如何判断给定的图是否

正好包含一个循环，
环上的每个节点都是树的根。

好消息是，假设您的图是连通的，那么如果属性 (1) 为真，那么属性 (2) 也为真！要了解这是为什么，请想象从该循环中删除任何边。现在你有一个没有循环的连通图，它是一棵树。这意味着每个节点，而不仅仅是循环中的节点，都可以被认为是根。

关于这个的好处是有一个非常好的算法来确定一个图是否连通并且只包含一个循环。首先，计算图中的边数。如果图确实连通并且恰好包含一个圈，那么边的数量应该恰好等于节点的数量。（一棵树的节点比边多一个，而你已经添加了一条边）。如果不是这种情况，请停止 - 答案是否定的。

从那里，您知道您拥有正确数量的节点和边。你只需要检查图是否连通，你可以在图上使用 DFS 或 BFS 来做到这一点。

这样做的好处是，如果您正确实施它，运行时间将为 O(n)，其中 n 是节点数，与边数无关。毕竟，如果看到多于n条边，就可以停止搜索了。

希望对您有所帮助！

从无向图中的树根检测循环

Detecting a cycle from tree's roots in an undirected graph

c++

algorithm

tree

graph-theory

undirected-graph