BFS

🙅‍♂️휴대폰으로 볼 때 혹시 글자나 숫자가 화면에 다 안나오면, 휴대폰 가로로 돌리시면 됩니다

BFS(Breadth-First Search) 란 너비 우선 탐색 으로
자료를 찾을 때 "수직" 방향으로 자료를 검색하는 DFS와 달리, “수평” 방향으로 자료를 검색한다

자 BFS는 맨 처음시작부터 수평방향으로 탐색을 한다고 했으니 아래 순서와 같을 것이다
A->B->C->D->E->F->G->H->I->J 를 1->2->3->4->5->6->7->8->9->10 같은 오름차순이라 생각하자

python 구현

graph = dict()

graph['Onion'] = ['Rice_ball', 'Poo']
graph['Rice_ball'] = ['Onion', 'Egg']
graph['Poo'] = ['Onion', 'Celery', 'Tofu', 'Pumpkin']
graph['Egg'] = ['Rice_ball', 'Kimchi', 'Peach']
graph['Kimchi'] = ['Egg']
graph['Peach'] = ['Egg']
graph['Celery'] = ['Poo']
graph['Tofu'] = ['Poo']
graph['Pumpkin'] = ['Poo', 'Tomato']
graph['Tomato'] = ['Pumpkin']

def bfs(graph, start_node):
    need_visited, visited = [], []
    need_visited.append(start_node)
     
    while need_visited:
        node = need_visited[0]
        del need_visited[0]

        # 노드가 방문하지 않았다면, 방문하고 visited에 추가해라
        if node not in visited:
            visited.append(node)
            # 그리고 해당 노드에 연결된 모든 이웃들을 need_visited에 추가해라
            # (append는 단일요소만 추가 extend는 여러개 추가) 
            need_visited.extend(graph[node])
    return visited

print(" -> ".join(bfs(graph, 'Onion')))

🫠발견한 문제

피드백을 받았는데 \(O(E^2)\) 즉 그래프 알고리즘의 시간 복잡도가 너무 길다고 한다
즉 실행시간이 겁나 길다는 것이다 그리하여 기존 코드에서 수정을 했다

기존 코드는 매번 visited 리스트에서 node가 있는지 확인하고, 이미 방문한 노드인 경우에만 visited에 추가해왔는데
하지만 이 방법은 매번 visited 리스트를 순회하여 확인해야 하므로 리스트의 크기에 비례하여 실행 시간이 증가할 수 있다
그리하여 대신에 visited를 집합(set)으로 구현하면 더 효율적일 수 있다.
why? -> 집합은 원소의 존재 여부를 빠르게 확인할 수 있기 때문에 검색 속도가 빠름

graph = dict()

graph['Onion'] = ['Rice_ball', 'Poo']
graph['Rice_ball'] = ['Onion', 'Egg']
graph['Poo'] = ['Onion', 'Celery', 'Tofu', 'Pumpkin']
graph['Egg'] = ['Rice_ball', 'Kimchi', 'Peach']
graph['Kimchi'] = ['Egg']
graph['Peach'] = ['Egg']
graph['Celery'] = ['Poo']
graph['Tofu'] = ['Poo']
graph['Pumpkin'] = ['Poo', 'Tomato']
graph['Tomato'] = ['Pumpkin']

def bfs(graph, start_node):
    need_visited, visited = [], set()
    need_visited.append(start_node)

    while need_visited:
        node = need_visited.pop(0)

        if node not in visited:
            visited.add(node)
            need_visited.extend(graph[node])

    return list(visited)

print(" -> ".join(bfs(graph, 'Onion')))

참고

BK_Paul    BFS 완벽 구현하기 - 파이썬