CareerCup

Using Depth First Search, if there is a back edge, it is a circle.

A Simple DFS is not sufficient here becoz you can have multiple parents for a single node. We will nead to massage the DFS algo used in the case of a tree slightly. The idea is, that if you come back to a node before all it's descendands are visited, there is a cycle... i think there is an algo called colored DFS or something.. ive seen it somewhere.. google

There's a rule in Combinatorics that relates to cycles. If I recall correctly, it has to do with Euler's circuit, verticies and their incoming/outgoing edges. Just pop open a good combo book and it should be in there somewhere.

Compute spanning trees from the graph by keeping track of the "depth" of each node (which is initially set to a sentinal value like -1 to indicate the node has not been visited). Follow each edge from the set of nodes you've last visited to directly connected unvisited nodes. If you encounter an unvisited node with a depth other than -1, you know you have cycle.

a graph without cycles is a tree if we assme only one connected unit. For a tree #vertices = #edges+1. maybe we do a dfs and count the edeges and vertices?

Topological sort can tell you if there's a cycle in a graph.

You can also detect if there's a cycle in a graph using DFS. You use DFS but with a few tweaks. Basically each node has 3 possible states, Not Explored, Explored, Completely Explored instead of 2. You also mark the pop when the stack pop. It's an interesting solution.

From Wikipedia:

Q ? Set of all nodes with no incoming edges
while Q is non-empty do
remove a node n from Q
output n
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into Q
if graph has edges then
output error message (graph has a cycle)

Koha - Topological sort won't work if the graph is undirected. So, in that case a tweaked DFS should do the job.

This should work:
Pseudo Code:

bool IsCircular(Array<Node> nodes)
{
foreach(Node node in nodes)
node.Visited = false;
foreach(Node node in nodes)
{
if(FindRecCirc(node))
return true;
}
return false;
}


bool FindRecCirc(Node n)
{
if(n.Visited)
return true;
n.Visited = true;
foreach(Node t in n.Neighbors)
{
if(FindRecCirc(t))
return true;
}
n.Visited = false;
return false;
}

If the graph is not directional, then doing a bfs can help us find the cycle in the graph.

This queue structure can be used .
Struct node
{
int inqueue;
int visited;
node* link;
}

Now if u reach a particular situation while doing bfs that you access a node that is in the queue(using the inqueue flag) and is also visited(using visited flag), you can say that there is a loop.

One can modify the BFS algorithm ..
BFS(source)
{
set discovered[source] = true;
int i = 0;
Initialise list l[0] with s
while( l[i] not empty)
{
initialise l[i+1]
get element := from l[i];
for each node adjacent to element
{
if discovered[node] == false
{add to l[i+1]
set discovered[node] = true
}
else
{if discovered [node] == true // node already been prevously detected therefore cycle !
print("cycle");
return
}
}
i =i +1
}
}

The Following is an algorithm to find the strong component of a graph and this is a tweak of DFS. If we have a strong component in a graph, then we have a cycle.

S <- empty stack
i <- 0
for(all x in V) 
do 
{
	num(v)<-0
}
for (all x in V)
do
{
	if (num(x) = 0) 
		then 
		STRONG(x);
}

STRONG(v)
{
	i<-i + l;
	lowlink(v)<-i
		push v onto the stack S
		for (all w in adj(v))
		{
			num(v)<-i;
			if (num(w) = 0)
			{
				STRONG(w)
					lowlink( v)<-min(lowlink( v), lowlink( w))
			}

			else if (num(w) < num(v) )
			{
				if (w in S)
					( lowLink(v)<-min(Lowlink(v), num(w)));
			}
		}
		if (Lowlink(v) = num(v))
		{
		pop vertices off the stack while num(stack top)> num(v)
		all those vertices popped off the stack are output as a strong component
		}
end STRONG

indenting rathi's code...

One can modify the BFS algorithm  .. 
BFS(source) 
{ 
	set discovered[source] = true; 
	int i = 0; 
	Initialise list l[0] with s 
		while( l[i] not empty) 
		{ 
			initialise l[i+1] 
			get element := from l[i]; 
			for each node adjacent to element 
			{ 
				if discovered[node] == false       
				{
					add to l[i+1] 
					set discovered[node] = true 
				} 
				else 
				{
					if discovered [node] == true // node already been prevously detected therefore cycle ! 
						print("cycle"); 
					return   
				} 
			} 
			i =i +1 
		} 
}

Use coloring(array) in DFS. If the node has been visited already, mark it as such.

you can detect cycles in directed graphs by using the DFS algorithm. (Depth-first-search)

For example consider the following directed graph with the vertices A,B,C,D,E,F,G,H:

C->B
B->A
C->D
D->E
D->G
E->F
F->G
G->H
H->D

I guess you want to graph this on a piece of paper

Let's say that every vertice is marked as "white".
We can only move to "white" vertices from now on.

Now, let's assume our DFS algorithm starts at C (to keep it simple).

We mark C as "gray" and move to B.
We mark B as "gray" and move to A.
We mark A as "gray" and we can't get any further here, so we mark A as "black" and move back to B which we will also mark as "black", since there is no way away from B other than moving to A again which is already "black".
Now, we move back to C which we will leave "gray", since there is still an open way away from C. We move from C to D.
We mark D as "gray" and move to E.
We mark E as "gray" and move to F.
We mark F as "gray" and move to G.
We mark G as "gray" and move to H.
We mark H as "gray" and move to D, which is "GRAY". This means that D is part of the actual path that is being considered by our DFS algorithm. We found a circle!!! This means that whenever we find a vertice (by moving forward) which is marked "gray" we have a cycle, and we then can terminate with return value "true" or whatever

This is supposed to be a short example, you should read over some more detailed description of DFS if you don't understand this. Every vertice in DFS has 3 states, "white", "gray" or "black". You can also say "not processed", "being processed", "processed" or whatever...it's up to you.

This algorithm also works if a directed graph is not strongly connected.

@ daniel J ...superb explanation

If we just want to know the existence of loops, then we can use adjacency matrix instead of adjacency list. Let M be the matrix, then the (i,j) entrie of M^k is the number of paths of length k from i to j. If there is a nonzero entry on the diagonal, then there is a loop.

can hare and tortoise algorithm work here?