from queue1 import Queue
from stack1 import Stack

class GNode:
    def __init__(self, vertex=None):
        self.vertex=vertex
        self.link=None

class Graph:
    def __init__(self):
        #인접 리스트로 구현
        self.adjacency_list=[]
        #방문 여부 체크
        self.visited=[]

    def add_vertex(self, vnum=1):
        self.adjacency_list.extend([None for _ in range(vnum)])
        self.visited.extend([False for _ in range(vnum)])
    
    def __add_node(self, vertex, node):
        cur=self.adjacency_list[vertex]
        #아직 에지가 하나도 없다면
        if not cur:
            self.adjacency_list[vertex]=node
        else:
            while cur.link:
                cur=cur.link
            cur.link=node

    def insert_edge(self, u, v):
        unode=GNode(u)
        vnode=GNode(v)

        self.__add_node(u, vnode)
        self.__add_node(v, unode)

    def init_visited(self):
        for i in range(len(self.visited)):
            self.visited[i]=False

    def bfs(self, v):
        
        ## step1) 큐를 하나만든다.
        ## step2) 큐에다가 첫번째 인덱스(시작 정점)를 삽입한다.
        ## step3) visited라는 array에 전부 false로 채워져 있는데
        ##        visited의 v에 True를 할당한다.
        ## step4) 큐가 비어있을때까지 while문이 돌것이다.
        ## step5) 큐에서 v를 하나 받아오는데 이 방식을 큐에서 dequeue하는 방식
        ## step6) v를 방문했다고 체크 (print문)
        ## step7) adjacency_list를 u로 할당하여 얻어온다.
        ## step8) u가 방문하지 않았으면 visited를 True로 바꿔준다.
        ## step9) u를 u.link로 만들어준다.
        
        q=Queue()
        #방문 체크 리스트를 초기화한다
        #O(v)
        self.init_visited()

        #첫번째 정점을 큐에 넣고
        #방문 체크
        q.enqueue(v)
        self.visited[v]=True
        
        # 방문
        print(v, end="  ")

        while not q.empty():
            v=q.dequeue()
            #인접 리스트를 얻어온다
            u=self.adjacency_list[v]
            while u:
                #아직 방문하지 않은 노드라면
                #큐에 넣고 방문 체크!
                if not self.visited[u.vertex]:
                    q.enqueue(u.vertex)
                    self.visited[u.vertex]=True
                u=u.link

    def __dfs_recursion(self, v):
        #방문
        print(v, end="  ")
        #방문 체크
        self.visited[v]=True

        u=self.adjacency_list[v]
        while u:
            if not self.visited[u.vertex]:
                self.__dfs_recursion(u.vertex)
            u=u.link

    def dfs(self, v):
        self.init_visited()
        self.__dfs_recursion(v)

    def iter_dfs(self, v):
        ## iter : 결국에는 while문이나for문 쓰겠다.
        ## v는 스타팅 포인트
        
        """
        시작 정점으로 돌아가 
        더 이상 방문할 정점이 없어야 종료
        """
        
        s=Stack() 
        # 스텍을 이용할 것이기 때문에 스텍을 하나 만듬
        
        self.init_visited() 
        ## 내부적으로 visited라는 함수를 이용해서 visit 배열을 false로 초기화

        s.push(v)
        ## 방문 체크 및 방문
        self.visited[v]=True
        print(v, end="  ")

        ## 스텍이 비어있지 않는 이상 계속 반복됨
        while not s.empty():
            
            is_moved = False
            
            v = s.peek()
            ## pop을 한다는 것은 스텍을 날려서 전단계로 돌아간다는 
            ## 의미니까 아직은 그럴 단계는 아니고 그냥 peek로 현재 위치를 받아옴
            
            ## v와 연결된 모든 인접 리스트를 받아온다.
            u = self.adjacency_list[v]
            ## u로 받아온것은 adjacency의 single_linked_list로 되어 있다.
            
            while u:
                
                if not self.visited[u.vertex]:
                    ## u가 아직 방문하지 않았다면
                    
                    s.push(u.vertex)
                    #방문 체크 및 방문
                    
                    self.visited[u.vertex]=True
                    ## 다음 노드로 이동했다는 것을 의미함
                    
                    print(u.vertex, end="  ")
                    #아직 방문하지 않은 정점을 방문했으므로
                    
                    is_moved=True
                    ## 방문했다는 의미는 이동을 했다는 의미이므로 is_moved를
                    ## True로 만든다.
                    
                    break
                    
                u = u.link
            
            if not is_moved: 
                ## while을 빠져나왔음에도 불구하고 is_move가 false라는 의미는
                ## 이동할 곳이 없다는 의미이므로 pop해서 back해주면 된다.
                s.pop()
                

## < visited >
## 배열이고 노드 6개가 [F,F,F,F,F,F]로 되어 있으며 인덱스가 vertex다
## 방문했으면 False가 True로 바뀐다

## < is_moved >
## 노드가 갈 수 있는 곳을 다 갔는가를 체크하는 용도

g=Graph()
g.add_vertex(6)
g.insert_edge(1, 0)
g.insert_edge(0, 3)
g.insert_edge(3, 4)
g.insert_edge(4, 2)
g.insert_edge(2, 5)

#예상 출력 결과 : 3  0  4  1  2  5
g.bfs(3)

#예상 출력 결과 : 3  0  1  4  2  5
g.dfs(3)

g.iter_dfs(3)