24. 그래프(Graph) - 너비 우선 검색(Breadth First Search)

현재 정점과 인접한 정점 중 방문하지 않은 정점을 '큐'에 넣고 하나씩 방문하면서 위의 문장을 반복합니다. 

 

깊이 우선 검색과 비교했을 때 스택, 큐 외에는 차이가 없습니다. 

 

귀차니즘으로... list를 queue로 사용했습니다. 

 

https://docs.python.org/ko/3/tutorial/datastructures.html#using-lists-as-queues

리스트를 큐로 사용하는 것도 가능한데, 처음으로 넣은 요소가 처음으로 꺼내지는 요소입니다 (《first-in, first-out》); 하지만, 리스트는 이 목적에는 효율적이지 않습니다. 리스트의 끝에 덧붙이거나, 끝에서 꺼내는 것은 빠르지만, 리스트의 머리에 덧붙이거나 머리에서 꺼내는 것은 느립니다 (다른 요소들을 모두 한 칸씩 이동시켜야 하기 때문입니다).
큐를 구현하려면, 양 끝에서의 덧붙이기와 꺼내기가 모두 빠르도록 설계된 collections.deque 를 사용하세요. 

class Graph:
    def __init__(self):
        self.graph = {}

    def add(self, v, w):
        self.graph.setdefault(v, {w})
        self.graph[v].add(w)
        self.graph.setdefault(w, {v})
        self.graph[w].add(v)

    def show(self):
        for node in self.graph:
            print(node, '->', self.graph[node])

    def bfs(self, start):
        queue = [start]
        marked = {start}

        while queue:
            v = queue.pop(0)
            print('Visited vertex:', v)
            for w in self.graph[v]:
                if w not in marked:
                    queue.append(w)
                    marked.add(w)

g = Graph()
g.add(0, 1)
g.add(0, 3)
g.add(1, 2)
g.add(3, 4)
g.add(1, 3)

g.show()
print('--')
g.bfs(0)
print('--')
g.bfs(1)

0 -> {1, 3}
1 -> {0, 2, 3}
3 -> {0, 1, 4}
2 -> {1}
4 -> {3}
--
Visited vertex: 0
Visited vertex: 1
Visited vertex: 3
Visited vertex: 2
Visited vertex: 4
--
Visited vertex: 1
Visited vertex: 0
Visited vertex: 2
Visited vertex: 3
Visited vertex: 4

 

for문을 사용하지 않고... 

class Graph:

    def __init__(self):
        self.graph = {}

    def add(self, v, w):
        self.graph.setdefault(v, {w})
        self.graph[v].add(w)
        self.graph.setdefault(w, {v})
        self.graph[w].add(v)

    def show(self):
        for node in self.graph:
            print(node, '->', self.graph[node])

    def bfs(self, start):
        queue = [start]
        marked = set()  # marked를 비운 상태로 시작합니다.
        while queue:
            v = queue.pop(0)
            if v not in marked:
                print('Visited vertex:', v)
                marked.add(v)
                queue.extend(self.graph[v].difference(marked))