# CSPT17 Lecture 11
# Depth-first

adjList = {
    1: {2, 3},
    2: {4},
    3: {4},
    4: {1}
}

def dftRecursive(startingNode, graph):
    visited = set()
    dftRecursiveHelper(startingNode, graph, visited)
    
def dftRecursiveHelper(node, graph, visited):
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dftRecursiveHelper(neighbor, graph, visited)

def dfsIterative(startingNode, destinationNode, graph):
    stack = deque()
    stack.append(startingNode)
    visited = set()
    
    while len(stack) > 0:
        currNode = stack.pop()
        if not currNode in visited:
            visited.add(currNode)
            if currNode == destinationNode:
                print('found node')
                return
                
            for neighbor in graph[currNode]:
                stack.append(neighbor)

# Breadth-first

def bfs(graph, startingNode, destinationNode):
    queue = deque()
    visited = set()
    visited.add(startingNode)
    queue.append(startingNode)
    while len(queue) > 0:
        currNode = queue.popleft()
        print(f"visiting node {currNode}")
        if currNode == destinationNode:
            print(f"found the destination node {currNode}")
            return currNode
        for neighbor in graph[currNode]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)