CODEWITHSUNDEEP
pythongraphdepth-first-search
user1928543
user1928543

Reputation: 45

Is cycle in graph?

I have this structure

class Node():
    def __init__(self, name):
        self.name=name
        self.adjencyList=[]
        self.visited = False

class Edge():
    def __init__(self, inNode, outNode):
        self.inNode=inNode
        self.outNode=outNode

this lists:

nodes = []
edges = []
uniqueNodes = []
listOfVisitedNodes = []

And I want to check is in graph is cycle. I'm doing it with DFS alghoritm - if I visit node which is visited yet, in graph is cycle. There is my alghoritm:

def DFS(node):
  node.visited = True
  listOfVisitedNodes.append(node)
  uniqueNodes = listOfVisitedNodes
  if len(set(uniqueNodes))==len(nodes):
     return True
  else:
    for i in node.adjencyList:
        if len(listOfVisitedNodes)==1:
            if listOfVisitedNodes[-1] != i:                
                if i in listOfVisitedNodes:                 
                    return False                    
                else:
                    DFS(i)
        else:
            if listOfVisitedNodes[-2] != i:                 
                if i in listOfVisitedNodes:                 
                    return False                    
                else:
                    DFS(i)
def isCycle():
    if DFS(nodes[0]):
        print 'there is no cycle'
    else:
        print 'there is cycle'

But I got still the same error - the alghoritm told me that in graph is allways cycle, doesnt matter what is the input. Thanks in advance for your your help guys.

Upvotes: 0

Views: 328

Answers (1)

Ignacio Vazquez-Abrams
Ignacio Vazquez-Abrams

Reputation: 799310

You forgot to return the result of the recursion.

return DFS(i)

Upvotes: 3

Related Questions