Detect cycle in an undirected graph | GeeksforGeeks
X. DFS: time O(V+E)
The time complexity of the union-find algorithm is O(ELogV). Like directed graphs, we can use DFS to detect cycle in an undirected graph in O(V+E) time. We do a DFS traversal of the given graph.
For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle.
If v is visited, and not current node's parent node(this is an undirected graph) ==> cycle found.
Difference from: Detect Cycle in a Directed Graph
http://massivealgorithms.blogspot.com/2014/07/detect-cycle-in-directed-graph.html
https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-undirected-graph-using-dfs/
X. DFS: time O(V+E)
The time complexity of the union-find algorithm is O(ELogV). Like directed graphs, we can use DFS to detect cycle in an undirected graph in O(V+E) time. We do a DFS traversal of the given graph.
For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle.
If v is visited, and not current node's parent node(this is an undirected graph) ==> cycle found.
Difference from: Detect Cycle in a Directed Graph
http://massivealgorithms.blogspot.com/2014/07/detect-cycle-in-directed-graph.html
https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-undirected-graph-using-dfs/
- Do DFS from every vertex. (please read DFS here).
- During DFS, for any current vertex ‘x’ (currently visiting vertex) if there an adjacent vertex ‘y’ is present which is already visited and no ‘y’ is not a direct parent of ‘x’ then there is a cycle in graph.
- Why not parent:
- Let’s assume, vertex ‘x’ and ‘y’ and we have edge between them. x—-y.
- Now do DFS from ‘x’, once you reach to ‘y’, will do the DFS from ‘y’ and adjacent vertex is ‘x’ and since its already visited so there should be cycle but actually there is no cycle since ‘x’ is a parent of ‘y’. That is why we will ignore visited vertex if it is parent of current vertex.
static class Graph {
int vertices;
LinkedList<Integer>[] adjList;
public Graph(int vertices) {
this.vertices = vertices;
adjList = new LinkedList[vertices];
for (int i = 0; i < vertices; i++) {
adjList[i] = new LinkedList<>();
}
}
public void addEdge(int source, int destination) {
// add forward edge
adjList[source].addFirst(destination);
// add reverse edge
adjList[destination].addFirst(source);
}
public boolean isCycle() {
boolean result = false;
// visited array
boolean[] visited = new boolean[vertices];
// do DFS, from each vertex
for (int i = 0; i < vertices; i++) {
if (visited[i] == false) {
if (isCycleUtil(i, visited, -1)) {
return true;
}
}
}
return result;
}
boolean isCycleUtil(int currVertex, boolean[] visited, int parent) {
// add this vertex to visited vertex
visited[currVertex] = true;
// visit neighbors except its direct parent
for (int i = 0; i < adjList[currVertex].size(); i++) {
int vertex = adjList[currVertex].get(i);
// check the adjacent vertex from current vertex
if (vertex != parent) {
// if destination vertex is not its direct parent then
if (visited[vertex]) {
// if here means this destination vertex is already visited
// means cycle has been detected
return true;
} else {
// recursion from destination node
if (isCycleUtil(vertex, visited, currVertex)) {
return true;
}
}
}
}
return false;
}
}
In directed graph, the back edge may point to parent node.// A recursive function that uses visited[] and parent to detect// cycle in subgraph reachable from vertex v.bool Graph::isCyclicUtil(int v, bool visited[], int parent){ // Mark the current node as visited visited[v] = true; // Recur for all the vertices adjacent to this vertex list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { // If an adjacent is not visited, then recur for that adjacent if (!visited[*i]) { if (isCyclicUtil(*i, visited, v)) return true; } // If an adjacent is visited and not parent of current vertex, // then there is a cycle. else if (*i != parent) return true; } return false;}// Returns true if the graph contains a cycle, else false.bool Graph::isCyclic(){ // Mark all the vertices as not visited and not part of recursion // stack bool *visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; // Call the recursive helper function to detect cycle in different // DFS trees for (int u = 0; u < V; u++) if (!visited[u] && isCyclicUtil(u, visited, -1)) return true; return false;}
X. Union-Find Algorithm | Set 1 (Detect Cycle in a an Undirected Graph)
We have also discussed a union-find algorithm for cycle detection in undirected graphs. The time complexity of the union-find algorithm is O(ELogV).
Note that the implementation of union() and find() is naive and takes O(n) time in worst case. These methods can be improved to O(Logn) using Union by Rank or Height.
https://algorithms.tutorialhorizon.com/graph-find-cycle-in-undirected-graph-using-disjoint-set-union-find/
We can't use UF for directed graph.
X. Detect Cycle in a Directed Graph using colors
https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-a-directed-graph-using-colors/
https://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
Read full article from Detect cycle in an undirected graph | GeeksforGeeks
We have also discussed a union-find algorithm for cycle detection in undirected graphs. The time complexity of the union-find algorithm is O(ELogV).
Note that the implementation of union() and find() is naive and takes O(n) time in worst case. These methods can be improved to O(Logn) using Union by Rank or Height.
https://algorithms.tutorialhorizon.com/graph-find-cycle-in-undirected-graph-using-disjoint-set-union-find/
- The makeset operation makes a new set by creating a new element with a parent pointer to itself.
- Then process each edge of the graph and perform find and Union operations to make subsets using both vertices of the edge.
- If find operation on both the vertices returns the same parent (means both vertices belongs to the same subset) then cycle is detected.
static class Edge {
int source;
int destination;
public Edge(int source, int destination) {
this.source = source;
this.destination = destination;
}
}
static class Graph {
int vertices;
LinkedList<Edge>[] adjList;
ArrayList<Edge> allEdges = new ArrayList<>();
Graph(int vertices) {
this.vertices = vertices;
adjList = new LinkedList[vertices];
for (int i = 0; i < vertices; i++) {
adjList[i] = new LinkedList<>();
}
}
public void addEgde(int source, int destination) {
Edge edge = new Edge(source, destination);
adjList[source].addFirst(edge);
allEdges.add(edge); // add to total edges
}
public void makeSet(int[] parent) {
// Make set- creating a new element with a parent pointer to itself.
for (int i = 0; i < vertices; i++) {
parent[i] = i;
}
}
public int find(int[] parent, int vertex) {
// chain of parent pointers from x upwards through the tree
// until an element is reached whose parent is itself
if (parent[vertex] != vertex)
return find(parent, parent[vertex]);
;
return vertex;
}
public void union(int[] parent, int x, int y) {
int x_set_parent = find(parent, x);
int y_set_parent = find(parent, y);
// make x as parent of y
parent[y_set_parent] = x_set_parent;
}
public boolean isCycle() {
// create a parent []
int[] parent = new int[vertices];
// makeset
makeSet(parent);
// iterate through all the edges and keep making the sets
for (int i = 0; i < allEdges.size(); i++) {
Edge edge = allEdges.get(i);
int x_set = find(parent, edge.source);
int y_set = find(parent, edge.destination);
// check if source vertex and destination vertex belongs to the same set
// if in same set then cycle has been detected else combine them into one set
if (x_set == y_set)
return true;
else
union(parent, x_set, y_set);
}
// if here, means cycle was not found
return false;
}
}
http://www.geeksforgeeks.org/union-find/We can't use UF for directed graph.
class Graph{ int V, E; // V-> no. of vertices & E->no.of edges Edge edge[]; // /collection of all edges class Edge { int src, dest; }; // Creates a graph with V vertices and E edges Graph(int v,int e) { V = v; E = e; edge = new Edge[E]; for (int i=0; i<e; ++i) edge[i] = new Edge(); } // A utility function to find the subset of an element i int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } // A utility function to do union of two subsets void Union(int parent[], int x, int y) { int xset = find(parent, x); int yset = find(parent, y); parent[xset] = yset; } // The main function to check whether a given graph // contains cycle or not int isCycle( Graph graph) { // Allocate memory for creating V subsets int parent[] = new int[graph.V]; // Initialize all subsets as single element sets for (int i=0; i<graph.V; ++i) parent[i]=-1; // Iterate through all edges of graph, find subset of both // vertices of every edge, if both subsets are same, then // there is cycle in graph. for (int i = 0; i < graph.E; ++i) { int x = graph.find(parent, graph.edge[i].src); int y = graph.find(parent, graph.edge[i].dest); if (x == y) return 1; graph.Union(parent, x, y); } return 0; }}
Note that the implementation of union() and find() is naive and takes O(n) time in worst case. These methods can be improved to O(Logn) using Union by Rank or Height.
BFS
Why DFS and not BFS for finding cycle in graphs
Depth first search is more memory efficient than breadth first search as you can backtrack sooner.
Once DFS finds a cycle, the stack will contain the nodes forming the cycle. The same is not true for BFS, so you need to do extra work if you want to also print the found cycle.
Also if your graph is directed then you have to not just remember if you have visited a node or not, but also how you got there.
http://stackoverflow.com/questions/4464336/pseudocode-to-find-cycles-in-a-graph-using-breadth-first-search
n an undirected graph, it's a traditional BFS that aborts and reports a cycle found when it reaches a node previously marked as visited. You can find pseudocode for BFS here.
In a directed graph, it gets trickier, since you have to remember which way were you walking when you reached the node, and the spatial complexity disadvantage over DFS gets even worse.
Depth first search is more memory efficient than breadth first search as you can backtrack sooner.
Once DFS finds a cycle, the stack will contain the nodes forming the cycle. The same is not true for BFS, so you need to do extra work if you want to also print the found cycle.
Also if your graph is directed then you have to not just remember if you have visited a node or not, but also how you got there.
http://stackoverflow.com/questions/4464336/pseudocode-to-find-cycles-in-a-graph-using-breadth-first-search
n an undirected graph, it's a traditional BFS that aborts and reports a cycle found when it reaches a node previously marked as visited. You can find pseudocode for BFS here.
In a directed graph, it gets trickier, since you have to remember which way were you walking when you reached the node, and the spatial complexity disadvantage over DFS gets even worse.
bool isCyclicConntected(vector<int> adj[], int s, int V, vector<bool>& visited) { // Set parent vertex for every vertex as -1. vector<int> parent(V, -1); // Create a queue for BFS queue<int> q; // Mark the current node as visited and enqueue it visited[s] = true; q.push(s); while (!q.empty()) { // Dequeue a vertex from queue and print it int u = q.front(); q.pop(); // Get all adjacent vertices of the dequeued // vertex s. If a adjacent has not been visited, // then mark it visited and enqueue it. We also // mark parent so that parent is not considered // for cycle. for (auto v : adj[u]) { if (!visited[v]) { visited[v] = true; q.push(v); parent[v] = u; } else if (parent[u] != v) return true; } } return false; } bool isCyclicDisconntected(vector<int> adj[], int V) { // Mark all the vertices as not visited vector<bool> visited(V, false); for (int i = 0; i < V; i++) if (!visited[i] && isCyclicConntected(adj, i, V, visited)) return true; return false; }
Each edge is considered at most twice (once for each of its end vertices), and since we go over every vertex of the graph, the overall complexity is O(V+E).
def is_cyclic_graph(G): Q = [] V = G.vertices() # initially all vertices are unexplored layer = { v: -1 for v in V } for v in V: # v has already been explored; move on if layer[v] != -1: continue # take v as a starting vertex layer[v] = 0 Q.append(v) # as long as Q is not empty while len(Q) > 0: # get the next vertex u of Q that must be looked at u = Q.pop(0) C = G.vertex_neighbors(u) for z in C: # if z is being found for the first time if layer[z] == -1: layer[z] = layer[u] + 1 Q.append(z) elif layer[z] >= layer[u]: return True return FalseX. Detect Cycle in a Directed Graph using colors
https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-a-directed-graph-using-colors/
https://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
WHITE : Vertex is not processed yet. Initially
all vertices are WHITE.
GRAY : Vertex is being processed (DFS for this
vertex has started, but not finished which means
that all descendants (ind DFS tree) of this vertex
are not processed yet (or this vertex is in function
call stack)
BLACK : Vertex and all its descendants are
processed.
While doing DFS, if we encounter an edge from current
vertex to a GRAY vertex, then this edge is back edge
and hence there is a cycle.
