CODEWITHSUNDEEP
c++graphdepth-first-search
Morpheus
Morpheus

Reputation: 3523

Detect a cycle and also get the members of the cycle in an Undirected Graph

I ma trying to find if an undirected graph has a cycle or not. and if it does have a cycle, get the members of the cycle.

I understand that getting all the cycles is much more difficult but I was wondering when a cycle is a detected, I can get the members of that cycle.

bool isThereACycle()
{
    std::stack<std::pair<int, int>> mystack;
    mystack.push(std::make_pair(0, -1));
    std::vector<bool> visited(N, false);  // N is the number of nodes
    visited[0] = true;

    while (!mystack.empty()) {
        int v = mystack.top().first;
        int f = mystack.top().second; // parent node
        mystack.pop();

        auto& edges = adj[v];
        for (auto it = edges.begin(); it != edges.end(); it++) 
        {
            int w = *it;
            if (!visited[w]) 
            {
                mystack.push(std::make_pair(w, v));
                visited[w] = true;
            } else if (w != f) 
            {
                return true;
            }
        }
    }
    return false;
}

The above code detects the cycles but I am unable to find the members associated with the cycle. is there a way to modify it slightly to ask get the members?

Upvotes: 0

Views: 665

Answers (1)

t sz
t sz

Reputation: 46

Yes, it is. If you store the parent of each node and when you find a cycle just go backwards while you don't reach the point where you found the cycle. Another part of the solution was, that you set a node visited if you processed it in the outer while.

bool isThereACycle()
{
    std::stack<std::pair<int, int>> mystack;
    mystack.push(std::make_pair(0, -1));
    std::vector<bool> visited(N, false);  // N is the number of nodes
    std::vector<int> parent(N, -1);

    while (!mystack.empty()) {
        
        int v = mystack.top().first;
        int f = mystack.top().second; // parent node
        visited[v] = true;
        mystack.pop();

        auto& edges = adj[v];
        int szamlalo = 0;
        for (auto it = edges.begin(); it != edges.end(); it++, szamlalo++) 
        {
            int w = *it;
            if (!visited[w]) 
            {
                mystack.push(std::make_pair(w, v));
                parent[w] = v;
            } else if (w != f) 
            {
                int current = v;
                while(current != w){
                    result.push_back(current);
                    current = parent[current];
                    mystack.pop();
                }
                result.push_back(current);
                return true;
            }
        }
        
        
    }
    return false;
}

Upvotes: 2

Related Questions