Find cycle/loop in the graph – method 1

August 2, 2017August 2, 2017 by omt

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

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;

	}

}

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() {