- Write a program to detect cycle in an undirected using BFS?
Algorithm:
-
Create a recursive function that takes the edge and color array (this
can be also kept as a global variable)
-
Mark the current node as GREY.
-
Traverse all the adjacent nodes and if any node is marked GREY then
return true as a loop is bound to exist.
-
If any adjacent vertex is WHITE then call the recursive function for
that node. If the function returns true. Return true.
-
If no adjacent node is grey or has not returned true then mark the
current Node as BLACK and return false.
<script>
var WHITE = 0, GRAY = 1, BLACK = 2;
class Graph
{
constructor(ver)
{
this.V = ver;
this.adjList = Array.from(
Array(this.V), () =< Array(this.V));
}
}
function addEdge(g, u, v)
{
g.adjList[u].push(v);
}
function DFSUtil(g, u, color)
{
color[u] = GRAY;
for(var iN of g.adjList[u])
{
if (color[iN] == GRAY)
return true;
if (color[iN] == WHITE &&
DFSUtil(g, iN, color) == true)
return true;
}
color[u] = BLACK;
return false;
}
function isCyclic(g)
{
var color = Array(g.V);
for(var i = 0; i < g.V; i++)
{
color[i] = WHITE;
}
for(var i = 0; i < g.V; i++)
{
if (color[i] == WHITE)
{
if (DFSUtil(g, i, color) == true)
return true;
}
}
return false;
}
var g = new Graph(4);
addEdge(g, 0, 1);
addEdge(g, 0, 2);
addEdge(g, 1, 2);
addEdge(g, 2, 0);
addEdge(g, 2, 3);
addEdge(g, 3, 3);
if (isCyclic(g))
document.write("Graph contains cycle");
else
document.write("Graph doesnt' contain cycle");
</script>
