[Section 4] 그래프와 큐의 혼합 _ 방문 상태 체크

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

방문 순서를 저장하는 알고리즘은 이후의 탐색 기법 중 DFS, BFS라는 알고리즘에서 필요한 알고리즘이다. 이 방문 순서 알고리즘은 큐와 그래프 알고리즘을 응용하여 생성이 가능하고 다양한 자료구조를 응용의 필요성에 대해 알려준다.

1.  배열 큐에 저장된 방문 순서 _ 예시 그래프와 큐

먼저 다음의 그래프 예시를 보자.

인접 행렬 그래프와 표 예시

 

위의 행렬에서 0으로 표기된 정보가 접근 가능하다는 의미를 나타낸다. 그리고 위 경우에서는 메모리 관점에서 인접 리스트로 구성하는 편이 더 나을 것이다. 따라서 인접 리스트 방식으로 구현하고자 한다.

 

이제 방문 순서에 대한 정보를 배열 큐로 나타내보자. 배열 큐의 리스트가 다음과 같은 방문 순서를 지칭한다고 가정하자. 

 

" [3,4,2,1] "

 

방문 순서를 큐로 정의함에 따라서 벌텍스의 방문 정보를 나타내는 알고리즘을 만들어보자.

2.  방문 정보 나타내기 _ 인접 리스트 그래프

방문 순서의 정보를 큐 리스트로 구현하고, 큐 리스트를 매개 변수로 받아 방문 정보를 나타내는 그래프 알고리즘을 생성할 수 있다. 이전의 벌텍스 클래스에 방문 상태를 체크하는 isV 변수를 추가하자.

 

예시 코드:

class Vertex:
    def __init__(self,node):
        self.node=node
        self.adjacent={}
        self.isV=False

...

 

False 이면 방문하지 않은것이고, True 이면 방문했던 벌텍스라는 의미가 된다. 위의 코드와 추가로 함수를 정의하면, 큐와 인접 리스트 그래프를 응용한 방문 체크 함수를 만들 수 있다.

 

def Acess(G,Q):
    current=Q.deQ()
    if current !=None:
        G.Dictionary[current].setisV()

def CheckA(G):
    check=[]
    for v in G:
         if v.isV==True:
             check.append(v.node)
    return check

 

다음의 결과를 통해서 방문 상태가 바뀌는 과정을 이해하도록 하자.

(CheckA함수를 통해서 방문 상태가 참인 벌텍스를 모두 리턴 한 결과이다. )

 

코드 결과 : 방문 상태 변화의 이해