-
Notifications
You must be signed in to change notification settings - Fork 0
/
cycle.cpp
127 lines (98 loc) · 2.33 KB
/
cycle.cpp
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
122
123
124
125
126
127
#include <iostream>
#include "Graph.cpp"
using namespace std;
//A class to find out if an undirected graph has a cycle or not
class Cycle {
private:
//An array to keep track of visited vertices
bool *visited;
//A flag to mark if there is a cycle in a graph or not
bool hasCycle;
//Number of vertices
int n;
//Keep track of parent of a vertex in DFS traversal
int *edgeTo;
//last edge in the cycle
int i;
int j;
public:
Cycle(Graph & g) : n( g.N() ) {
//Allocate space for the visited array
visited = new bool[n];
//Iniialize the vertices as not visited
for(int v = 0; v < n; v++) {
visited[v] = false;
}
//Initialize the flag as false
hasCycle = false;
//Allocate space for edgeTo array
edgeTo = new int[n];
//Visit all the unvisited vertices
for(int s = 0; s < n; s++ ) {
//Do a DFS from an unvisited vertex
if( !visited[s] )
dfs(g, s, s);
}
}
//DFS is called with v and u (which is parent of v)
void dfs(Graph & g, int v, int u) {
//Mark v as visited
visited[v] = true;
//Visit the neighbors of v
for(LinkedList<int>::iterator it = g.adjList(v).begin(); it != g.adjList(v).end(); it ++) {
//Neighbor of v
int w = *it;
//if w is not visited -- start a DFS from w
if( !visited[w] ) {
//Call DFS with w and it's parent
dfs(g, w, v);
edgeTo[w] = v;
}
//if w is visited and w is not v's parent
//Since the graph is undirected v's parent is also on v's adjacency list
else if( w != u ) {
hasCycle = true;
j = w;
i = v;
}
}
}
//Returns if the graph has a cycle or not
bool HasCycle() {
return hasCycle;
}
//If there is a cycle -- this returns the cycle
void getCycle(LinkedList<int> & cycle) {
if( hasCycle ) {
cycle.add( i );
for(int x = j; x != i; x = edgeTo[x]) {
cycle.add(x);
}
cycle.add( i );
}
}
//The destructor
~Cycle() {
delete [] visited;
delete [] edgeTo;
}
};
//Test if an undirected graph has a cycle or not
int main() {
Graph g("graph3.txt");
Cycle cycle(g);
if( cycle.HasCycle() ) {
cout<<"The graph has a cycle.\n";
LinkedList<int> lList;
cycle.getCycle(lList);
cout<<"The cycle is: \n";
for(LinkedList<int>::iterator it = lList.begin(); it != lList.end(); it ++) {
cout<<*it<<" ";
}
cout<<endl;
}
else {
cout<<"The graph has no cycle.\n";
}
return 0;
}