# Given a node in a directed graph, write a function that determines if there is a cycle in the graph.

Finding all cycles in graph

http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph

Similar Question:
Given an undirected graph G=(V,E) with n vertices ( |V| = n ), how do you find if it contains a cycle in O(n) ?

Note-(I)
Depth first search with backtracking should work here. Keep an array of boolean values to keep track of whether you visited a node before. If you run out of new nodes to go to (without hitting a node you have already been), then just backtrack and try a different branch.

The DFS is easy to implement if you have an adjacency list to represent the graph. For example adj[A] = {B,C} indicates that B and C are the children of A.

For example, pseudo-code below. "start" is the node you start from.

dfs(adj,node,visited): 
  if (visited[node]): 
    if (node == start): 
      "found a path" 
    return; 
  visited[node]=YES; 
  for child in adj[node]: 
    dfs(adj,child,visited)
  visited[node]=NO;

Call the above function with the start node:

visited = {}
dfs(adj,start,visited)

If in Python::

def dfs(adj, node, visitedbool):
    if (visited[node]):
        if (node == start):
            print("found a path")
            return visitedbool
    visited[node]=True
      for child in adj[node]:
        dfs(adj,child,visited)
    visited[node]=False

# adj[A] = [B,C]  is a dictionary
# visitedbool is a dictionary, key is each node, and vale is bool type

Note-(II)depth first search solves it. If an unexplored edge leads to a node visited before, then the graph contains a cycle. This condition also makes it O(n), since you can explore maximum n edges without setting it to true or being left with no unexplored edges.


Note-(III) This could devolve into an O(n^2) algorithm if you aren't careful? If you check for a node visited before by keeping all of the nodes in a linked list (new nodes to the end) then you'll have to scan your node list (the scan is O(n) in itself) on each check. Ergo - O(n^2).If you mark each node, though, it is definitely O(n)

Note-(IV) Now, how fast is the algorithm? ---> O(V)   (although dfs is O(|V|+|E|) -- so paricular!? )
First, imagine the graph has no cycles. The number of edges is then O(V), the graph is a forest, goal reached.
Now, imagine the graph has cycles, and your searching algorithm will finish and report success in the first of them. The graph is undirected, and therefore, the when the algorithm inspects an edge, there are only two possibilities: Either it has visited the other end of the edge, or it has and then, this edge closes a circle. And once it sees the other vertex of the edge, that vertex is "inspected", so there are only O(V) of these operations. The second case will be reached only once throughout the run of the algorithm.

 Note(V)the assumption that the graph is connected can be handful. thus, you can use the proof shown above, that the running time is O(|V|). if not, then |E|>|V|. reminder: the running time of DFS is O(|V|+|E|).

[[[Another Related Topic:]]]
a undirected graph with about 100 nodes and about 200 edges. One node is labelled 'start', one is 'end', and there's about a dozen labelled 'mustpass'.
I need to find the shortest path through this graph that starts at 'start', ends at 'end', and passes through all of the 'mustpass' nodes (in any order).

----->>>In TSP, the objective is to find the shortest cycle that visits all the vertices (a Hamiltonian cycle) -- it corresponds to having every node labelled 'mustpass'.
In your case, given that you have only about a dozen labelled 'mustpass', and given that 12! is rather small (479001600), you can simply try all permutations of only the 'mustpass' nodes, and look at the shortest path from 'start' to 'end' that visits the 'mustpass' nodes in that order -- it will simply be the concatenation of the shortest paths between every two consecutive nodes in that list.
In other words, first find the shortest distance between each pair of vertices (you can use Dijkstra's algorithm or others, but with those small numbers (100 nodes), even the simplest-to-code Floyd-Warshall algorithm will run in time). Then, once you have this in a table, try all permutations of your 'mustpass' nodes, and the rest.
Something like this:

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

(Of course that's not real code, and if you want the actual path you'll have to keep track of which permutation gives the shortest distance, and also what the all-pairs shortest paths are, but you get the idea.)
It will run in at most a few seconds on any reasonable language :)
[If you have n nodes and k 'mustpass' nodes, its running time is O(n³) for the Floyd-Warshall part, and O(k!n) for the all permutations part, and 100^3+(12!)(100) is practically peanuts unless you have some really restrictive constraints.]

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥
http://stackoverflow.com/questions/526331/cycles-in-an-undirected-graph 
http://stackoverflow.com/questions/222413/find-the-shortest-path-in-a-graph-which-visits-certain-nodes