图：如何使用DFS检测非直接图中的周期

以下是我的DFS实现，现在我想实现它，以便可以检测图中是否存在任何循环（以下代码基本上是用于查找连接元素的数量）图：如何使用DFS检测非直接图中的周期

#include <iostream> 
#include <vector> 
using namespace std; 

vector <int> adj[10]; 
int visited[10]; 
bool flag=false; 

void dfs(int s) { 
    visited[s] = 0; 
    for(int i = 0;i < adj[s].size();++i) { 
    if(visited[adj[s][i]] == -1) 
     dfs(adj[s][i]); 
    else if (visited[adj[s][i]] ==1){ 
     flag=true; 
     // cout<<"g"; 
     return; 
    } 
    } 
    visited[s]=1; 
} 

void initialize() { 
    for(int i = 0;i < 10;++i) 
    visited[i] = -1; 
} 

int main() { 
    int nodes, edges, x, y ; 
    cin >> nodes;      //Number of nodes 
    cin >> edges;      //Number of edges 
    for(int i = 0;i < edges;++i) { 
    cin >> x >> y;  
    adj[x].push_back(y);     //Edge from vertex x to vertex y 
    adj[y].push_back(x);     //Edge from vertex y to vertex x 
    } 

    initialize();       //Initialize all nodes as not visited 

    for(int i = 1;i <= nodes;++i) { 
    if(visited[i] == false)  { 
     dfs(i); 
    } 

    } 
    if (flag) 
     cout<<"Graph contains cycles"<<endl; 
    else 
     cout<<"No cycles"<<endl; 
    return 0; 
}

我不知道如何实现它，任何人都可以帮助我。

编辑：我试图实现它。不知道我要去的地方错了

来源

2017-10-14 Yathartha Joshi

我初始化调用后改变了循环：

for(int i = 0;i < nodes;++i) { 
    if(visited[i] == -1)  { 
    dfs(i); 
    } 
}

你的代码没有开始检查，因为在visited每个元素被设置为-1，因此跳过。所以这个改变确实奏效。

我建议看看你的全局变量adj和visted的大小，如果可能的话使它们成为本地的。当输入11个或更多节点时，此代码将停止工作。

编辑的问题：“你能告诉我，我该如何检查断开的图？”

更改同一回路这样：

int nr_of_graphs = 0; 
for(int i = 0;i < nodes;++i) { 
    if(visited[i] == -1)  { 
    ++nr_of_graphs; 
    dfs(i); 
    } 
} 
cout << "Nr of disconnected subgraphs " << nr_of_graphs << endl;

dfs(i)被每尚未访问的节点。因此，计算从main调用此函数的次数，给出断开子图的数量。

来源

2017-10-14 08:45:26 Haas

是啊对不起，这是一个愚蠢的错误，我发了:)谢谢！ –

你能告诉我如何检查断开的图吗？ –

图：如何使用DFS检测非直接图中的周期

回答

相关问题