Graphique: Comment détecter les cycles dans un graphe indirect à l'aide de DFS

Question

Voici ma mise en œuvre DFS, maintenant je veux l'implémenter de manière à pouvoir détecter s'il y a des cycles présents dans un graphe ou non (le code ci-dessous est essentiellement utilisé pour trouver le nombre d'éléments connectés)

#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; 
} 

Je ne suis pas sûr de savoir comment le mettre en œuvre, quelqu'un pourrait me aider.

Modifier: J'ai essayé de l'implémenter. Je ne sais pas où je vais mal

Answer 1

J'ai changé la boucle après l'appel d'initialisation:

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

Votre code n'a pas commencé parce que la vérification de chaque élément dans le visited a été fixé à -1 et par conséquent sauté. Donc, avec ce changement, cela fonctionne.

Je suggère de regarder la taille de vos variables globales adj et visted, les rendre locales si possible. Lorsque 11 nœuds ou plus sont entrés, ce code cessera de fonctionner.

Modifier pour la question « Pouvez-vous me dire comment puis-je vérifier pour le graphique déconnecté? »

Modifier la même boucle à ceci:

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) est appelé pour chaque noeud pas encore visité. Donc compter le nombre de fois que cette fonction est appelée à partir de main, donne le nombre de sous-graphes déconnectés.