c++ - 在无向图中从树的根检测循环

Question

我想确定给定图是否具有我想要的结构。我想要的结构是，如果给定图的树的根形成一个循环，则输出为true，否则为false。
这是一个示例图:

它有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)为true，则属性(2)也是如此!要了解为什么会这样，请想象从该循环中删除任何边。现在您有了一个没有循环的连接图，它是一棵树。这意味着每个节点，而不仅仅是循环中的节点，都可以被视为根。

这样做的好处是，有一种非常好的算法可以确定图形是否已连接并包含一个周期。首先，计算图中的边数。如果图确实是连接的并且仅包含一个周期，则边的数量应恰好等于节点的数量。 (一棵树比边缘多一个节点，并且您已经添加了一个边缘)。如果不是这种情况，那就停下来-答案是否定的。

从那里，您知道节点和边的数量正确。您只需要检查图形是否已连接，就可以通过图形上的DFS或BFS进行连接。

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

希望这可以帮助!