Menu
I have a hw problem that asks for an algorithm that detects if there is any cycle in any undirected graph that contains any given edge 'E'. The algorithm should run in O(N) linear time.
The problem I have is that I don't know where to start. I have some simple sample graphs but I dont know where to go from there.
Any hints?
273
Cycle detection The existence of a cycle in directed and undirected graphs can be determined by whether depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge). All the back edges which DFS skips over are part of cycles.
There is a cycle in a graph only if there is a back edge present in the graph. Depth First Traversal can be used to detect a cycle in a Graph, DFS for a connected graph produces a tree.
An undirected graph can contain an edge which belongs to all of its cycles graph only if this graph has a single cycle. Let's look at an example. Edge (2,3) belongs to two cycles, but you always can find a third cycle to which such an edge doesn't belong.
Use DFS from every unvisited node. Depth First Traversal can be used to detect a cycle in a Graph.
Take out that edge (u,v) from G. 1. Run BFS to see if v is still reachable from u. 2. if yes, then the original graph has a cycle containing e. otherwise there is not.
153
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
