Cycle Detection in A Graph

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉

Concept of
Strongly Connected Components (SCC)
is very similar to that of Cycles. Please visit the chapter
Strongly Connected Components (SCC) as well,
after having a strong grasp on
Finding Cycles
and
Cycle Detection Using DFS
to have a very wellrounded knowledge.
You would be amazed to see how many different kinds of solutions you are able to think of for
a given problem.
For any nodes 𝑎 and 𝑏, the node 𝑎 and 𝑏 belong to the same cycle if and only if 𝑎 and 𝑏 are strongly connected.
In this article we will be discussing about five ways of detecting cycle in a graph:

Using Topological Sort for Directed Graph: If the graph does not have a topological sort then the graph definitely
contains one or more cycles. We have an entire chapter on this.
Please see the chapter "Topological Sort: DFS, BFS and DAG".

Using BFS for Undirected Graph: If you see a crossedge, there is a cycle.
You can still use BFS to detect cycle in a Directed Graph, but in that case you also have to use Topological Sorting along with BFS. Please refer to the Topological Sort by BFS section of the article "Topological Sort: DFS, BFS and DAG".
In this approach you won't need to find crossedge in this approach. Here you try your best to build a topological ordering for whichever vertices possible in the graph, and then at last you check if the topological ordering contains all the vertices in the graph. If there cycles in the graph the vertices participating in the cycle(s) will not be present in the topological sort, resulting in the size of the list of vertices present in the topological sort less than the total number of vertices present in the graph. If (number of vertices present in the topological ordering) != total number of vertices present in the graph, then that indicates that there is at least one cycle present in the graph, because if there were no cycle present in the graph then the topological sort would contain all the vertices of the graph.

Using DFS for both Directed and Undirected Graph: A backedge determines a cycle.
Read the chapter "Cycle Detection Using DFS"
to know more about this.

Using UnionFind and Kruskal’s Algorithm for both Directed and Undirected Graph:
Kruskal’s algorithm is all about avoiding cycles in a graph. It uses UnionFind technique for doing that. You can use the same for detecting cycles in a graph.
You start building a spanning tree starting with an empty set of edges and picking one edge at random. If the both the vertices of a new unvisited edge that you are visiting happens to belong to the same component then you have a cycle.
The algorithm should look like below:for each unvisited edge (u, v) in E { if(Find(u) = Find(v)) // u and v belong to the same set already { print "Cycle Detected"; break; } else { Union(u, v); // put u and v in the same set } }
How Would You Know What Kind of Edge You Are Dealing With?
Here’s the trick:
Let’s consider an edge XY.
Back Edge: If discovered(y) == true and processed(y) == false, then XY is a Back Edge.
In this case, node Y has been discovered and is in visiting state but has not been fully processed. So node X happens to be one of the descendents of Y. A edge coming back in from a descendent is definitely a Back Edge.
Forward Edge: If
1. processed(y) == true, and
2. entryTime(x) < entryTime(y)
then XY is a Forward Edge.
Cross Edge: If
1. processed(y) == true,
2. entryTime(y) < entryTime(x)
then XY is a Cross Edge.
Kruskal’s Algorithm:
Those who already remember ins and outs of Kruskal’s Algorithm can skip the rest of this article. Those who need to brush up Kruskal’s Algorithm go on reading till the last.
Kruskal’s Algorithm is a Greedy Approach to construct a Minimum Spanning Tree, in which edges are considered in nondecreasing order of cost. This interpretation is that the set t of edges so far selected for the spanning tree be such that it is possible to complete t into a tree.Thus t may not be a tree at all stages in the algorithm. In fact, it will generally only be a forest since the set of edges t can be completed into a tree iff there are NO cycles in t.
Let’s go over the pseudocode now:
Algorithm Kruskal(E, cost, n, t) // E is the set of edges in G. G has n vertices, cost[u, v] is the // cost of edge (u, v). t is the set of edges in the minimumcost // spanning tree. An array consisting of all the edges of the // minimumcost spanning tree is returned. { Construct a minheap out of the edge costs either using Heapify or PriorityQueue API in Java. // Each vertex should be in its own set initially for i := 1 to n do parent[i] := 1; Take an array Arr of size E to return the edges of the spanning tree; i := 0, mincost := 0.0; while ((i < n  1) and (heap not empty)) do { Delete a minimum cost edge (u, v) from the heap and reheapify; j := Find(u); k := Find(v); // Make sure including the edge UV in the set doesn't // introduce a cycle. if (j != k) then { i := i + 1; t[i, 1] := u; t[i, 2] := v; Union(j, k); mincost := mincost + cost[u, v]; Put edge UV in Arr; } } if (i != n  1) then write ("No Spanning Tree"); else return Arr; }
In more simplified form:
t is an empty set; while ((t has less than n  1 edges) and (E is not empty)) do { Choose an edge uv from E of lowest cost; Delete edge uv from E; if uv does NOT create a cycle in t then add uv to t; else discard uv; }
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.