Find cycle/loop in the graph – method 1
Find below algorithm to find loop/cycle in graph, Here in each stage I am checking for child node visited state. If any of the parent node has more than one child with visited state then it means graph has a loop. We can also use Disjoint Set (Or Union-Find) which I’ll show you in next article.
Algorithm to find cycle in graph
|
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 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
package com.omt.learn.algo; import java.util.HashSet; import java.util.Set; import java.util.TreeSet; import com.omt.learn.algo.util.graph.Graph; import com.omt.learn.algo.util.graph.Node; import com.omt.learn.algo.util.graph.State; public class FindCycleInGraph { public static void main(String[] args) { System.out.println("Is graph contains cycle :" + isGraphContainsCycle(generateLoopGraph())); System.out.println("Is graph contains cycle :" + isGraphContainsCycle(generateNonLoopGraph())); } public static boolean isGraphContainsCycle(Graph graph) { for (Node parentNode : graph.getVertices()) { parentNode.setState(State.VISITED); int numberOfVisitedChild = 0; for (Node childNode : parentNode.getAdjacent()) { if (childNode.isVisited()) { if (numberOfVisitedChild == 0) { numberOfVisitedChild++; } else { return true; } } } } return false; } public static Graph generateLoopGraph() { Graph graph = new Graph(); Node a = new Node("A"); // 0 Node b = new Node("B"); // 1 Node c = new Node("C"); // 2 Node d = new Node("D"); // 3 Node e = new Node("E"); // 4 Node f = new Node("F"); // 5 Node g = new Node("G"); // 6 Node h = new Node("H"); // 7 Node i = new Node("I"); // 8 a.addAdjacent(b); a.addAdjacent(c); b.addAdjacent(d); b.addAdjacent(a); d.addAdjacent(b); d.addAdjacent(e); d.addAdjacent(f); e.addAdjacent(d); e.addAdjacent(f); e.addAdjacent(g); f.addAdjacent(e); f.addAdjacent(d); f.addAdjacent(g); g.addAdjacent(e); g.addAdjacent(f); c.addAdjacent(a); c.addAdjacent(h); h.addAdjacent(c); graph.addVertex(a); graph.addVertex(b); graph.addVertex(c); graph.addVertex(d); graph.addVertex(e); graph.addVertex(f); graph.addVertex(g); graph.addVertex(h); graph.addVertex(i); return graph; } public static Graph generateNonLoopGraph() { Graph graph = new Graph(); Node a = new Node("A"); // 0 Node b = new Node("B"); // 1 Node c = new Node("C"); // 2 Node d = new Node("D"); // 3 Node e = new Node("E"); // 4 Node f = new Node("F"); // 5 Node g = new Node("G"); // 6 Node h = new Node("H"); // 7 Node i = new Node("I"); // 8 a.addAdjacent(b); a.addAdjacent(c); b.addAdjacent(d); b.addAdjacent(a); d.addAdjacent(b); d.addAdjacent(f); e.addAdjacent(i); e.addAdjacent(g); f.addAdjacent(d); f.addAdjacent(g); g.addAdjacent(e); g.addAdjacent(f); c.addAdjacent(a); c.addAdjacent(h); h.addAdjacent(c); i.addAdjacent(e); graph.addVertex(a); graph.addVertex(b); graph.addVertex(c); graph.addVertex(h); graph.addVertex(d); graph.addVertex(f); graph.addVertex(g); graph.addVertex(e); graph.addVertex(i); return graph; } } |
Find graph utility here
Find graph utility
