CODEWITHSUNDEEP
algorithmgraphtree
Kyle
Kyle

Reputation: 154

Special case in singly connected graph

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.

Upvotes: 0

Views: 108

Answers (1)

gimme_danger
gimme_danger

Reputation: 798

Is there any special case which can not be solved by using DFS-visit for each node?

No, dfs must perfectly solve your problem.

Keep trying to find a bug. This code might help you. It computes all connected components in undirected graph.

Upvotes: 0

Related Questions