General Graph Cycle Detection (Confirm my Answer please) [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this question

The problem:

An undirected graph is unicyclic if it contains exactly one cycle. Describe an O( |V| + |E| ) algorithm for determining whether or not a given graph, G is unicyclic.

My solution:

int i = 0

Run a modified DFS on G, where we increment i everytime we decide not to visit a vertex because it has already been visited.

After DFS is done, if i==1, graph is unicyclic.

I thought this solution would work but am wondering if there is a counter example that would prove it false. If anyone could clarify that would be great, Thanks.

Answer 1

Does your graph consists of a single connected component?

In this case just count vertices and edges and check |V| - |E| = 0

Otherwise count the number of connected components O(|V| + |E|), and check |V| - |E| = number of connected components - 1.

Remark: having more than one connected component is a counterexample to your algorithm.

Answer 2

"Increment i everytime we decide not to visit a vertex because 
it has already been visited."

I am quite unclear about what you are trying to do here.

Rather then this, how about this:

Perform DFS and count number of back edges.

A back edge is an edge that is from a node to itself (selfloop) or one of its 
ancestor in the tree produced by DFS.

If number of back edges ==1 then unicycle else not.

To count number of back edges, follow this algorithm.

To detect a back edge, we can keep track of vertices currently in recursion stack of 
function for DFS traversal. If we reach a vertex that is already in the recursion stack,
then there is a cycle in the tree. The edge that connects current vertex to the
vertex in the recursion stack is back edge