1) If the graph is undirected: Do a DFS/BFS, if you visit a previously visited node we have a cycle.
2) In a directed graph: a) Do a DFS and mark start and finish time for each node
b) Find back edges. Each back edge (u,v) has following property: start[u] <= start[v] and finish[v]<=finish[u]
c) Back edges => cycle
Important subtleties: 1) In the condition: start[u] <= start[v] and finish[v]<=finish[u], the equality corresponds to self edges, be sure to include equality if your graph can have self edges.
2) In the implementation of DFS is non-recursive, remember that a node is marked visited when it is popped from the stack and not when it is inserted in the stack.
while(stack s is not empty)
{
u = s.pop();
if(visited[u] ==true)
continue;
visited[u] = true;
for all nodes v adjacent to u
if(v is unvisited)
s.push(v)
}
http://www.spoj.com/problems/EPIC1304/
2) In a directed graph: a) Do a DFS and mark start and finish time for each node
b) Find back edges. Each back edge (u,v) has following property: start[u] <= start[v] and finish[v]<=finish[u]
c) Back edges => cycle
Important subtleties: 1) In the condition: start[u] <= start[v] and finish[v]<=finish[u], the equality corresponds to self edges, be sure to include equality if your graph can have self edges.
2) In the implementation of DFS is non-recursive, remember that a node is marked visited when it is popped from the stack and not when it is inserted in the stack.
while(stack s is not empty)
{
u = s.pop();
if(visited[u] ==true)
continue;
visited[u] = true;
for all nodes v adjacent to u
if(v is unvisited)
s.push(v)
}
http://www.spoj.com/problems/EPIC1304/
For undirected graph cycle detection, if we do a BFS we just need O(n) time. Why? Step1: If we found a visited node this implies there is a cycle in the undirected graph. Say we start from node 's' and as we are exploring edge (t,u) we find that visited(u) = true, implying u was visited before t. So, there is a path from s to t (as s is the source) and there is a different path from s to u, and therefore a cycle.
ReplyDeletestep2: We need to see atmost n edges. For every edge either we explore a new vertex or visit a previous visited one. So, we need to explore at most n edges before finding a previously visited node.