C++

Forum

 
DFS to detect cycle with selected nodes

tristanbox09 (13)
Hello guys,

I am trying to detect a cycle in a graph using DFS, but the only twist is that I have to input certain nodes from the graph, and from those nodes I have to see if a cycle is formed. I can get the normal DFS cycle detection down, but in the green comment I have my DFS for selected nodes I am passing in, but my issue is that it will always return a cycle regardless of whether the graph is actually a cycle or not.

For undirected graph 1, I am trying to see if nodes 4,5,6 form a cycle. Regardless of the edge connection (5,6) I still get a cycle detection which is wrong. Any help is greatly appreciated!! 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
  #include<iostream>
#include<list>
#include<vector>
#include<stack>

using namespace std;

class Graph {

private:

    int nodes;
    list<int>* adjlist;
    vector<bool> visited;

    // parent stores the parent node of the visited node, this is used
    // for finding cycle in an un-directed graph.
    vector<int> parent;

    bool cycle_present;

public:
    int count = 0;
    Graph() {
    }

    Graph(int arg_nodes) {

        this->nodes = arg_nodes;
        adjlist = new list<int>[nodes];
        visited.resize(nodes, false);
        parent.resize(nodes, -1);
        cycle_present = false;
    }

    ~Graph() {
        delete[] adjlist;
    }

    void AddEdge(int src, int dst, bool bidirectional) {

        adjlist[src].push_back(dst);

        if (bidirectional)
            adjlist[dst].push_back(src);
    }

    // Function detects cycle in an undirected graph
    //
    void DFS_DetectCycleInUndirectedGraph(int src, vector<int>& lucky) {

        visited[src] = true;

        for (auto& adj_node : lucky)
        {
            count++;
            if (count < lucky.size())
            {
                adj_node = lucky[count];
            }
            if (!visited[adj_node])
            {

                parent[adj_node] = src;
                DFS_DetectCycleInUndirectedGraph(adj_node, lucky);

            }
            else if (parent[src] != adj_node)
            {

                cycle_present = true;
                return;

            }
        }
    }

    bool IsCyclePresent() {
        return cycle_present;
    }
};

int main()
{
    Graph g1_undirected(7);

    /* Undirected graph 1
               0
              / \
             1   2
                / \
               3   4
                  / \
                 5 - 6 */
    g1_undirected.AddEdge(0, 1, true);
    g1_undirected.AddEdge(0, 2, true);
    g1_undirected.AddEdge(2, 3, true);
    g1_undirected.AddEdge(2, 4, true);
    g1_undirected.AddEdge(4, 5, true);
    g1_undirected.AddEdge(4, 6, true);
    g1_undirected.AddEdge(5, 6, true);

    vector<int> lucky;
    //lucky.push_back(0);
    //lucky.push_back(1);
    //lucky.push_back(2);
    //lucky.push_back(3);
    lucky.push_back(4);
    lucky.push_back(5);
    lucky.push_back(6);

    g1_undirected.DFS_DetectCycleInUndirectedGraph(lucky[0], lucky);  // (4, <4,5,6>)

    if (g1_undirected.IsCyclePresent()) {
        cout << "Cycle found in the undirected graph g1" << endl;
    }
    else {
        cout << "Cycle not found in the undirected graph g1" << endl;
    }
    return 0;
}
Last edited on
lastchance (6980)
Your question is very unclear. Please remove from your code any commented-out parts and any tests that are irrelevant to your problem.

"in my green comment" is hopelessly ambiguous here.
tristanbox09 (13)
@lastchance I am sorry, I removed the comments in my main. The block comment in the DFS function is for the selected nodes I pass into that function to see if those selected nodes form a cycle. The uncommented part in DFS works for a full DFS traversal...now I have to tweak it to see if selected nodes form a cycle (the code in green which doesnt work)
tristanbox09 (13)
So if I test <4,5,6> it should return no cycle ... but if I use the code which does a selected node traversal it prints that it has a cycle that is wrong... if I use the regular DFS traversal then it works fine ... I need to find a work around to have DFS work on selected nodes
lastchance (6980)
Your question is still unclear. You have two loop structures in DFS_DetectCycleInUndirectedGraph. Are you intending to run the first? The second (currently commented out)? Both?

Please remove everything that is irrelevant to your problem, and if you are asking about a fragment of code then don't put it in comments.

I don't know if you are referring to the part between /* and */ but you seem to be incrementing a variable count that was only initialised once when the object was created. Also, if adj_node is controlling your range-based loop then you shouldn't be setting its value mid-loop.
Topic archived. No new replies allowed.