“Iterative DFS Python” Code-Antworten

Iterative DFS Python

G = {
    'A': {'C'},
    'B': {'A'},
    'C': {'B', 'D', 'E'},
    'D': {},
    'E': {}
}

def getNeighbors(vertex):
    return list(G[vertex])

# iterative dfs in Python
def dfs(root, target):
    stk = [] # stack (LIFO)
    visited = set() # keep track of vertices we've seen before
    stk.insert(0, root) # push root to top of stack
    visited.add(root) # mark root (start point) as visited
    while len(stk): # while our stk is not empty
        top = stk.pop(0)
        if top == target: # is top of stk our target?
            return True # we found a path from root to target in our graph!
        for neighbor in getNeighbors(top): # you must write a 'getNeighbor' function
            # this function should return all the vertices connected to root
            if neighbor in visited: continue # don't revisit vertices!
            visited.add(neighbor) # mark neighbor as visited
            stk.insert(0, neighbor) # add neighbor to our stack
    
    return False # we went through every path from 'root' and didn't find 'target'

result = dfs('C', 'E')
print(result)