문과생이 이해한 파이썬 BFS(너비 우선 탐색)- 인접 행렬 버전

#c언어로 쉽게 풀어쓴 자료구조 연습문제를 파이썬 코드로 구현

MAX_QUEUE_SIZE=10
MAX_VERITICES=10   #정점

class CircleQueue:
    def __init__(self):
        self.front=0; self.rear=0
        self.queue=[None]*MAX_QUEUE_SIZE
    def is_empty(self):
        return self.front==self.rear
    def is_full(self):
        return (self.rear+1)%MAX_QUEUE_SIZE==self.front
    def enqueue(self, data):
        if self.is_full():
            print('큐가 포화상태입니다.'); return
        self.rear=(self.rear+1)%MAX_QUEUE_SIZE
        self.queue[self.rear]=data
    def dequeue(self):
        if self.is_empty():
            print('큐가 공백상태입니다.'); return
        self.front=(self.front+1)%MAX_QUEUE_SIZE
        return self.queue[self.front]
        
class BFS:
    def __init__(self):
        self.veritices_number=0   #정점의 개수
        self.adj_mat=[[False for j in range(MAX_VERITICES)] for i in range(MAX_VERITICES)]
        self.visited=[False]*MAX_VERITICES
        
    def insert_vertex(self):    #정점 삽입 
        if (self.veritices_number+1)>MAX_VERITICES:
            print('그래프: 정점의 개수 초가')
            return
        self.veritices_number+=1
        
    def insert_edge(self, start, end):   #간선 삽입 
        if (start>=self.veritices_number and end>=self.veritices_number):
            print('그래프: 정점 번호 오류')
            return
        self.adj_mat[start][end]=True
        self.adj_mat[end][start]=True
        
    def bfs_mat(self, v=0):
        Q=CircleQueue()
        self.visited[v]=True   #정점 v에 방문 표시 
        print('{} 방문 -> '.format(v), end=' ')
        Q.enqueue(v)       #시작 정점을 큐에 저장
        while not(Q.is_empty()):
            v=Q.dequeue()
            for w in range(self.veritices_number):
                if self.adj_mat[v][w] and not(self.visited[w]):
                    self.visited[w]=True      #방문 표시
                    print('{} 방문 -> '.format(w), end=' ')
                    Q.enqueue(w)
                    
if __name__=='__main__':
    bfs=BFS()
    for i in range(6):
        bfs.insert_vertex()
    bfs.insert_edge(0,2)
    bfs.insert_edge(2,1)
    bfs.insert_edge(2,3)
    bfs.insert_edge(0,4)
    bfs.insert_edge(4,5)
    bfs.insert_edge(1,5)
    
    print('**********너비 우선 탐색********')
    bfs.bfs_mat()

 

  대게 재밋게 공부한 BFS!!

 

---

<기본 정보>

 

 

 

 

 너비 우선 탐색은 시작 정점에서 가장 가까운 정점을 먼저 방문하고 멀리 떨어져있는 나중에 방문하는 순회 방법이다. 인접 행렬 버전과 인접 리스트 버전이 있다. 이 포스팅에서는 인접 행렬을 이용한 BFS를 포스팅하겠다!

 

 먼저 (a)를 잘 보자. 

 

 

 0은 현재 정점이고, 0과 이어져있는 정점으로는 1로 표시된 1,2,3이다. 그래서 0정점의 차수(연결된 인접 정점)은 3이 된다. (이런 식으로 행렬을 읽으면 되는데 앞에 설명 안 읽고 무작정 코드부터 읽다가 왜 행렬을 쓰는지 한참동안 이해 못햇었다... 바보ㅜㅜ) 

 

 

---

<초기화>

 

 초기화에는 3가지 요소가 필요하다. 

 

1. 정점의 개수를 세기위한 변수

2. 간선 연결을 확인하기 위한 2차원 리스트

3. 어떤 정점을 방문했는지 확인하기 위한 리스트

 

(2차원 리스트 사이즈가 10x10이라서 그냥 디버깅한 거 캡쳐해서 썻당... visted 리스트도 사이즈는 10이고 저 검은 디버깅 창을 잘보면 있다)

 

---

<정점 삽입>

 정점 삽입은 간단하다. 정점 개수를 세는 변수(veritices_number)에 1을 더해주면 된다. 전역 변수로 선언한 MAX_VERITICES보다 개수가 적어야 겠쥬??

 

 

---

<간선 삽입>

 간선 연결에 앞서 일단 start와 end로 입력받은 숫자가 현재 정점의 개수를 초과하진 않는지 확인한다. ppt에도 썻듯이 없는 정점을 연결할 순 없으니까!!

 

 

연결은 코드처럼 2차원 리스트(adj_mat)의 [start][end]와 [end][start]에 넣어준다. 왜 이렇게 넣어주나 싶었는데 무방향 그래프를 표현하기 위함이다. 

 

 무방향 그래프는 start 정점에서 end정점으로 갈 수도 잇고, end정점에서 start 정점으로도 갈 수 잇다. 

(방향 그래프는 반대로 start에서는 end를 갈 수 잇찌만, end에서는 start를 갈 수 없는 그래프를 말한다.) 

 

 tmi! 이렇게 간선을 삽입하다보니 2차원 리스트는 대칭 행렬이 된다! 

 

  모든 간선을 연결한 모습이다. 아까 BFS 행렬 읽는 법을 복습해보자.

 

1. 2차원 리스트의 0번째 행은 0번 정점을 의미하고, 열은 인접 정점들을 의미한다.

2. 현재 그래프만 보면 0과 연결된 인접 정점은 2와 4다.

3. 다시 0번째 행을 보면 2와 4만 True이다.

4. 이는 곧 0정점의 인접 정점은 2와 4라는 의미다!

 

 

---

<BFS : 너비 우선 탐색>

 

 여기서 왜 너비 우선 탐색할 때 자료구조 큐를 사용 하는지 알 수 있따ㅎㅎ

 일단 큐 객체를 선언해준다. 시작/현재 정점(v, 0)을 다음과 같은 연산을 실행 해준다. 

 

1. visited(해당 정점을 방문했는지 안 했는지, True or False로 표현한 리스트)에 True 표시

2. 큐에 삽입

 

 

 그리고 이때 0을 방문 햇따고 출력해준다. 그리고 Q에 시작 정점이 들어갔으므로 while문으로 들어간다. 

 

 

 

 while문의 내용은 간단하다.

 

1. 현재 정점(v)에 큐에 들어있는 값을 dequeue하여 저장

2. 현재 정점과 연결된 인접 정점을 행렬을 순회하며 찾는다. -> adj_mat[현재 정점][다른 정점들]

3. 만약 인접 정점을 찾았다면 그 정점(w)을 방문 햇는지 안 했는지도 확인한다.-> visitied[w]

4. 2,3번의 조건을 만족한다면, 시작 정점에 했던 연산을 해준다. 

  4-1. visited(해당 정점을 방문했는지 안 했는지, True or False로 표현한 리스트)에 True 표시

  4-2. 큐에 삽입

 

 

 여기서 왜 큐를 사용하는지 보이는가용?? 일단 방문한 인접 행렬들을 순서대로 큐에 저장하니까 다음 정점의 인접 행렬도 순서대로 순회할 수 있기 때문입니다!!! 

 

 

 자 0의 인접 정점은 2와 4이므로 2와 4를 큐에 삽입하고 visited에 True표시를 해줍니다. 그러면 while문이 끝이나고 0의 인접 정점 중 하나인 2를 dequeue하여 v(현재 정점)에 저장합니다. 

 

 

 

  그리고 또 조건 검사ㅎㅎ

 

 

 이 과정을 계속 반복하다보면 visited 리스트가 모두 True가 되는 순간이 오는데. 그러면 조건 검사를 할 필요가 없겠쥬?? 그러니까 계속 dequeue하면서 결국 Q가 모두 비어버리면 while문을 종료하고, BFS도 끝이 납니다!!

 

 

---

<출력 결과>

 

 

---

 사실 이거 하면서 큐의 front와 rear가 좀 헷갈렸다. 이래서 기초가 중요한 것 같다. 좀 헤매다가 틀린 걸 깨닫고 눈물을 머금고 ppt를 싹 다 수정해야 했다ㅜㅜ

 

front(선단) : 먼저 삽입된 데이터를 읽는다. 현재 front가 가리키는 자리는 없는 데이터 취급.

rear(후단) : 데이터를 삽입. 현재 rear가 가리키는 자리는 데이터가 이미 있음.