Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hi I was wondering if someone could help answer a question for me. I was working on a problem from my algorithms class that asks for an algorithm to determine whether or not a graph is singly connected. By singly connected it states the graph is connected i.e. there is a simple path from u-->v for all u,v in V and that there are at most one of these paths.

Oh I should mention this is a DAG.

The question is in the DFS section so I assume that want to use that the standard solution seems to be to do a DFS on every vertex and ensure that there are only forward, and tree edges in the solution this makes sense to me but I am wondering if anyone sees anything wrong with the following solution

Do a DFS on the graph the algorithm in my book stores a nodes parent when it finds it. After DFS finishes if all nodes have not been examined then we know that the graph is not connected so we can stop there.

Otherwise do a second DFS on the graph except this time do not set the parent node instead

White Nodes:

When we find a white node u ensure that u's parent is set as the current node we are looking at i.e. we discovered u from the current node in the first traversal otherwise we have 2 paths to u and we can return false.

Grey/Black Nodes:

Originally when we find an edge Grey-->Grey or Grey-->Black we essentially ignore it in the modified algorithm we would ensure that the grey node is set as grey or black nodes parent otherwise during the first traversal we discovered this node from somewhere else and there are two paths to the node return false.

The standard solution runs in V*(V+E) and mine would be 2(V+E) I can't imagine I randomly came up with an algo with marked improvement on the first instinct but I've thought about it for a while and it seems like mine would come up with the right solution.

If anyone could provide a counter example or explain why mine is wrong I greatly appreciate it.

share|improve this question
1  
Please add some punctuation to your question.. it's almost completely incomprehensible. –  Haile Dec 2 '12 at 14:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.