# CSPT25 Lecture 13

from collections import deque
class Graph:
    def __init__(self):
        self.adjList = {}
    def __repr__(self):
        return str(self.adjList)
    def addEdge(self, source, destination):
        if source not in self.adjList or destination not in self.adjList:
            return
        self.adjList[source].add(destination)
    def removeEdge(self, source, destination):
        if source not in self.adjList or destination not in self.adjList:
            return
        try:
            self.adjList[source].remove(destination)
        except:
            pass
    def edgeExists(self, source, destination):
        return destination in self.adjList[source]
    def addVertex(self, value):
        if value in self.adjList:
            return
        self.adjList[value] = set()
    def removeVertex(self, vertexToRemove):
        if vertexToRemove not in self.adjList:
            return
        self.adjList.pop(vertexToRemove)
        for (vertex, neighbors) in self.adjList.items():
            if vertexToRemove in neighbors:
                neighbors.remove(vertexToRemove)
    def dftIterative(self, startingNode):
        stack = deque()
        stack.append(startingNode)
        visited = set()
        res = []
        while len(stack) > 0:
            curr = stack.pop()
            if curr not in visited:
                visited.add(curr)
                res.append(curr)   
                for neighbor in self.adjList[curr]:
                    stack.append(neighbor)
        return res
    def dftRecursive(self, startingNode):
        visited = set()
        res = []
        self.dftRecursiveHelper(startingNode, visited, res)
        return res
    def dftRecursiveHelper(self, currNode, visited, res):
        visited.add(currNode)
        res.append(currNode)
        for neighbor in self.adjList[currNode]:
            if neighbor not in visited:
                self.dftRecursiveHelper(neighbor, visited, res)
    def bftIterative(self, startingNode):
        queue = deque()
        queue.append(startingNode)
        visited = set()
        res = []
        while len(queue) > 0:
            curr = queue.popleft()
            if curr not in visited:
                visited.add(curr)
                res.append(curr)   
                for neighbor in self.adjList[curr]:
                    queue.append(neighbor)
        return res
g = Graph()
g.addVertex(1)
g.addVertex(2)
g.addVertex(3)
g.addVertex(4)
g.addEdge(1, 2)
g.addEdge(1, 3)
g.addEdge(2, 4)
g.addEdge(3, 4)
g.addEdge(4, 1)
print(g.bftIterative(1))