I'm trying to write an algorithm to determine whether a giving graph is singly connected. The homework definition says that a singly connected graph means between two nodes, there is at most one simple path.
I see lots of answer here says that using DFS-visit for each node, and if there's a black node been visited, it means there are two simple paths. As a result, the given graph is not simply connected.
I rewrite DFS algorithm to achieve that, but the problem is it can solve all the given graph except one special case. I already consider the situation which there are multiple edges between two nodes, but it does not work.
So my question is that is there any special case which can not be solved by using DFS-visit for each node?
def dsf(self, source):
source.color = 'g'
for node in source.next:
if node.color == 'w':
if not self.dsf(node):
return False
elif node.color == 'b':
return False
source.color = 'b'
return True
if dsf encounter black node, it will return False and terminate the function.
def singly(self):
for node in self.nodes:
if not self.dsf(node):
return False
self.__clear()
return True
And then using this function to check each node in the graph. Self.__clear can reset all the node's color back to white.
The algorithms work for all the case except for one special case.
