My iterative dfs (cause why not) Python solution with adjacency list


  • 0
    S

    I wanted to see if I could come up with an iterative way to check cycles, which as it turns out requires a modification to the traditional iterative DFS method. To make sure that I am detected back edges correctly, I store the current edge being explored from a vertex on its stack frame, and don't pop the node off the stack until it has explored all its edges. This is similar to what is going on in the call stack of recursive DFS.

    class Solution(object):
        
        class Vertex:
            def __init__(self):
                self.edges = []
                self.visited = False
                self.first_visited = False
    
        def canFinish(self, numCourses, prerequisites):
            
            #create adjacency list
            verticies = [Solution.Vertex() for _ in range(numCourses)]
            for prereq in prerequisites:
                verticies[prereq[1]].edges.append(verticies[prereq[0]])
                
            #Runs dfs
            def hasCycle(v):
                stack = [[v, 0]]
                v.visited = True
                v.first_visited = True
                
                while len(stack):
                    curr = stack[-1][0]
                    nextEdge = stack[-1][1]
                    if nextEdge >= len(curr.edges): #we've visited all children
                        curr.visited = False
                        stack.pop()
                        continue
                    next = curr.edges[nextEdge]
                    if (next.visited):
                        return True
                    next.visited = True
                    next.first_visited = True
                    stack[-1][1] += 1
                    stack.append([next, 0])
                return False
                
            
            for v in verticies:
                if not v.first_visited:
                    if hasCycle(v):
                        return False
                        
            return True

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.