Задав неориентированный граф с V вершинами и E ребрами, проверьте, содержит ли он какой-либо цикл или нет.
Пример 1:
V = 5, E = 5
adj = {{1}, {0, 2, 4}, {1, 3}, {2, 4}, {1, 3}}
Output: 1
Объяснение: 
1->2->3->4->1 — цикл.
Решение: Tc — o(n), где n — количество узлов в матрице.
Пространственная сложность: o(n) для использования массива n размером visited[].
class Node {
int first;
int second;
public Node(int f, int s){
this.first = f;
this.second =s;
}
}
class Solution {
// Function to detect cycle in an undirected graph.
public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
// Code here
//cycle detection using breadth first search
// as in breadth first search we visit adjacent nodes of a given node,one by one
//we will use pair<Integer,Integer> to store current node and previous node of
//we will keep track of parent node of every given node . if next node is visited and it is parent node
// then its ok it just means that current nodes parent is visited , but if the next node is visited and
//its not equals to parent node, then it means that this node has already been visited by
// bread first traversal of some other node. Hence there must be a cycle in the graph.
//creating visited array
boolean visited[] = new boolean[V];// size is V for 0 based indexing
Arrays.fill(visited,false);
for(int i =0;i<V;i++){
if(!visited[i]){
if(cycle(i,adj,visited)) return true;
}
}
return false;
}
public boolean cycle(int n, ArrayList<ArrayList<Integer>> adj, boolean[] visited){
Queue<Node> queue = new LinkedList<>();
visited[n] = true;
queue.add(new Node(n,-1)); // since there is no parent of first node hence -1;
while(!queue.isEmpty()){
int node = queue.peek().first;
int parent = queue.peek().second;
queue.remove();
for(Integer adjNode: adj.get(node)){
if(!visited[adjNode]){
visited[adjNode] = true;
queue.add(new Node(adjNode,node));
}
else if(adjNode !=parent) {
return true;
}
}
}
return false;
}
}
Использование поиска по глубине:
class Solution {
// Function to detect cycle in an undirected graph.
public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
// we will use depth first search for solving this problem
//In this given problem
/*V = 5, E = 5
adj = {{1}, {0, 2, 4}, {1, 3}, {2, 4}, {1, 3}}
we will start with 0->1->3->4-> 1 , since 1 is already visited we can return
true meaning there is a cycle in the graph.
Here also we will use the concept of currentNode and parent node. Similar to breadh first search
*/
int visited[]= new int[V];
for(int i =0;i<V;i++){
if(visited[i]==0){
if(dfsCheckCycle(i,-1,visited,adj)) return true;
}
}
return false;
}
public boolean dfsCheckCycle(int node,int parent, int visited[], ArrayList<ArrayList<Integer>> adj){
if(visited[node] ==1) return true;
visited[node] =1;
for(Integer i : adj.get(node)){
if(dfsCheckCycle(i,node,visited,adj) && i!=parent) return true;
}
return false;
}
}
dfsCheckCycle() можно также записать как
public boolean dfsCheckCycle(int node,int parent, int visited[], ArrayList<ArrayList<Integer>> adj){
visited[node] =1;
for(Integer i : adj.get(node)){
if(visited[i] ==0){
if(dfsCheckCycle(i,node,visited,adj)) return true;
}
else if(i!=parent) return true;
}
return false;
}
Обнаружение циклов в направленном графе с помощью поиска по глубине
Если мы используем тот же подход, что и при обнаружении циклов в неориентированном графе с помощью dfs, то это не сработает.
Если мы используем тот же подход (обнаружение циклов с помощью dfs в неориентированном графе).
Мы начнем с 1->2->3->4->5 (до этого момента 1,2,3,4,5 уже посещены).
Затем мы вернемся к 3, затем 6->5, но в 5 уже посещено
мы проверим, является ли 5 равным родителем 6, что нет. Следовательно, будет возвращено true, что означает, что эта часть графа имеет цикл, что не верно.
Модификация:
Мы будем использовать тот же алгоритм поиска по глубине, который мы использовали в неориентированном графе, немного изменив его.
Мы будем использовать дополнительный массив посещений.
Поэтому, когда мы начнем с 1, мы пометим его как посещенный в visited[], а также в dfsVisited[].
Аналогично 1->2->3->4->5 будет помечен как посещенный в обоих массивах visited. Но после 5 мы вернемся к 3 и 5,4 будут помечены как непосещенные в массиве dfsVisited[] (хотя они останутся помеченными как посещенные в массиве visited[]).
Следовательно, когда мы достигнем 5 снова из 3->6>5 и 5 не будет помечен как посещенный в dfsVisited[].
Аналогично мы продолжим И, мы достигнем 7->8>9->7. Как только мы снова достигнем 7, мы проверим, посещена ли она в обоих массивах, если да (а это именно так), то мы вернем true, что означает наличие цикла в этом графе.
Временная сложность: O(N+E) мы обходим n узлов и E соседних узлов из этих N узлов.
Пространственная сложность: O(2N) для 2 посещенных массивов, + O(N) для вспомогательного пространства стека.
class Solution {
// Function to detect cycle in a directed graph.
public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
// code here
int visited[] = new int[V];
int dfsVisited[] =new int[V];
for(int i =0;i<V;i++){
if(visited[i]==0){
if(isCycleUtil(i,visited,dfsVisited,adj)) return true;
}
}
return false;
}
public boolean isCycleUtil(int n, int[] visited,int dfsVisited[], ArrayList<ArrayList<Integer>> adj){
visited[n] = 1;
dfsVisited[n] = 1;
for(Integer i : adj.get(n)){
if(visited[i]==0){
if(isCycleUtil(i,visited,dfsVisited,adj)) return true;
}
else if(dfsVisited[i]==1) return true;
}
dfsVisited[n] = 0;
return false;
}
}
Обнаружение циклов в направленном графе с помощью Breadth first Search
Мы будем использовать алгоритм Кана для обнаружения циклов в направленном графе.
Мы знаем, что алгоритм Кана используется для топологической сортировки.
Одна вещь, которая очень важна в отношении топологической сортировки — она не применима к циклическому графу.
Следовательно, мы попытаемся сгенерировать топологическую сортировку данного направленного графа, и если граф имеет цикл, то его топологическая сортировка не будет сгенерирована должным образом.
class Solution
{
//Function to return list containing vertices in Topological order.
static boolean hasCycle(int V, ArrayList<ArrayList<Integer>> adj)
{
//we will use Kahn's algorithm for getting topological sorting, it uses
//breadh first search algorithm
// we will be required to calculate the indegree of all the nodes;
int indegree[] = new int[V];
/// calculating indegrees of all the nodes
for(int i =0;i<V;i++){
for(Integer j : adj.get(i)){
indegree[j]++;
}
}
Queue<Integer> q = new LinkedList<>();
//putting those nodes in the queue whose indegrees are 0
//because these are the nodes that have no incoming edge to them hence they
//can be at the start of the topological sorting as it will not cause any issue
//because we are maintaining order of u followed by v where u->v (u has edge directed towards v)
for(int i =0;i<V;i++){
if(indegree[i]==0){
q.add(i);
}
}
int result[] = new int[V];
int index =0;
int count = 0;
while(!q.isEmpty()){
Integer i = q.remove();
result[index++] = i;
count++;
for(Integer node : adj.get(i)){
// here we re reducing the indegrees as the nodes that are alredy there
// the queue are getting removed hence there edges with the node 'node' will
//also be removed hence there indegrees will decrease by one
indegree[node]--;
//and as soon as there indegrees becomes 0 means they are independent now and they have no incoming edge to them
//hence they can be added to queue just like we did earlier.
if(indegree[node]==0){
q.add(node);
}
}
}
if(count!=V) return true; // it means graph has cycle
return false; // no cycle kahn's breadh first search algo worked and topological sorting of the graph was generated successfully
}
}