CareerCup

DFS will do

Topological sort for cycle detection.

To find a cycle in a graph, run DFS and look for a back edge. The existence of a back edges indicates the existence of a cycle.

To look for back edges, keep a running stack of your DFS. If an edge leads to a vertex that's in your current stack, that's a back edge and is a cycle.

//Assumption:The graph is in the form of an adjacency matrix.
//Time Complexity: O(v+e) where v is the number of vertices and e is the number of edges.
//Space: O(v);

public boolean hasCycle(boolean[][] adj)
{	
	if(adj==null||adj.length==0)
	{
		return false;
	}
	
	boolean[] visited=new boolean[adj.length];
	for(int i=0;i<visited.length;i++)
	{
		if(!visited[i])
		{
			boolean hasCycle=checkCycle(i,visited, adj, new HashMap<Integer,Boolean>());
			if(hasCycle)
			{
				return true;
			}
		}
	}
	return false;
}

private boolean checkCycle(int p, boolean[] v,boolean[][] m, HashMap<Integer,Boolean> mp)
{
	v[p]=true;
	mp.put(p,true);
	for(int i=0;i<m[p].length;i++)
	{
		if(m[p][i])
		{
			if(mp.containsKey(i))
			{
				return true;
			}
			if(![v])
			{
				boolean c=checkCycle(i,v,m,mp);
				if(c)
				{
					return true;
				}
			}
		}
	}
	return false;
}

I believe that the question is simplified and therefore you do not have to do a full blown DFS. For this problem you can get away with something like this (NOTE: not tested):

<pre>
Map<Node> visitedNodes = new HashMap<Node>();

public boolean isCycle( Node node ) {

Node existingNode = visitedNodes.put( node );
if( existingNode != null ) {

return true;

}

boolean cycleFound = false;

for( Node connectedNode : node.connectedNodes ) {

cycleFound = cycleFound || isCycle( connectedNode );

}

return cycleFound;

}
</pre>

If the graph were represented as an incidence matrix, you could simply check if the dimension of the null space is non-zero, which indicates the circuit rank of the graph.

f

Two traversals at once,
- Traverse the Graph using DFS picking up the node with immediate next depth
- Traverse the Graph using DFS picking up the node with next to next depth

If the faster traversal finishes itself ==> this is not a cyclic directed graph
Else if the two traversals meet at some point ==> this is a cyclic directed graph.

The complexity is same as DFS, just twice.

I believe that the question simplifies the implementation and you do not have to do a full blown DFS. This should do (NOTE: was not tested)

Map<Node> visitedNodes = new HashMap<Node>();

public boolean isCycle( Node node ) {

	Node existingNode = visitedNodes.put( node );
	if( existingNode != null ) {
		
		return true;
	
	}
	
	boolean cycleFound = false;
	
	for( Node connectedNode : node.connectedNodes ) {
	
		cycleFound = cycleFound || isCycle( connectedNode );
	
	}

	return cycleFound;
	
}

I believe that the question is simplified and therefore you do not have to do a full blown DFS. For this problem you can get away with something like this (NOTE: not tested):

Map<Node> visitedNodes = new HashMap<Node>();

public boolean isCycle( Node node ) {

	Node existingNode = visitedNodes.put( node );
	if( existingNode != null ) {
		
		return true;
	
	}
	
	boolean cycleFound = false;
	
	for( Node connectedNode : node.connectedNodes ) {
	
		cycleFound = cycleFound || isCycle( connectedNode );
	
	}

	return cycleFound;

}

I believe that the question is simplified and therefore you do not have to do a full blown DFS. For this problem you can get away with something like this (NOTE: not tested):

Map<Node> visitedNodes = new HashMap<Node>();

public boolean isCycle( Node node ) {

	Node existingNode = visitedNodes.put( node );
	if( existingNode != null ) {
		
		return true;
	
	}
	
	boolean cycleFound = false;
	
	for( Node connectedNode : node.connectedNodes ) {
	
		cycleFound = cycleFound || isCycle( connectedNode );
	
	}

	return cycleFound;
	
}