너비 우선 탐색 BFS ; Breadth First Search

기본적으로 ChatGPT를 이용하여 틀을 잡고 만든 것

너비 우선 탐색
맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법
더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용

너비우선탐색 1

질문: bfs(graph, start) 무방향 그래프와 시작 정점 start를 나타내는 사전 그래프를 가져와서 방문한 정점 목록을 너비 우선 순서로 반환합니다.

그래프의 꼭짓점에 0에서 N-1까지의 정수 레이블이 지정되어 있다고 가정합니다. 여기서 N은 꼭짓점의 총 개수입니다. graph 사전은 리스트의 리스트로 표현되며, 여기서 graph[i]는 정점 i에 인접한 정점의 리스트입니다.

For 예를 들어 정점이 0, 1, 2, 3이고 가장자리가 (0, 1), (0, 2), (1, 2), (2, 3)인 그래프는 [[ 1, 2], [0, 2], [0, 1, 3], [2]].

그래프가 연결되어 있고 정점에 번호가 매겨져 있다고 가정할 수 있습니다. 0부터 순차적으로 시작합니다.

def bfs(graph, start):
    # 방문 배열 생성 및 초기화
    visited = [False] * len(graph)
    # queue 배열 생성 및 방문할 노드 추가 start 추가
    queue = [start]
    # 첫 방문
    visited[start] = True
    # 방문한 리스트 작성, 순서 중요
    result = []
    
    # 이제 방문할 노드가 없으면 그만 둔다.
    while queue:
        # 가장 먼저 들어간 노드 방문
        vertex = queue.pop(0)
        # 방문한 리스트에 방문한 노드 추가
        result.append(vertex)
        
        # 방문한 노드에서 bfs 반복할 수 있도록 queue에 추가
        for neighbor in graph[vertex]:
            
            # 방문하게 될 때 한번 방문 했던 곳은 또 방문하지 않는다.
            if not visited[neighbor]:
                # 방문한 노드에 True 
                visited[neighbor] = True
                # 다음에 방문한 정점을 queue에 추가한다.
                queue.append(neighbor) 
    return result

graph = [[1, 2], [0, 2], [0, 1, 3], [2]]
start = 0
print(bfs(graph, start)) # Output: [0, 1, 2, 3]

[0, 1, 2, 3]

• 알고리즘
  1. 지금까지 방문한 정점을 추적하기 위해 방문한 목록을 초기화하는 것으로 시작 visited
  2. 여전히 방문해야 하는 정점을 추적하기 위한 목록 대기열. queue
  3. 또한 빈 목록 result를 초기화하여 방문한 정점을 순서대로 저장
  4. 먼저 시작 정점 start를 방문하여 대기열에 추가하여 방문한 것으로 표시
  5. 대기열에 정점이 있는 한 계속되는 루프에 들어감
  6. 반복할 때마다 큐에서 다음 정점을 빼서 result 목록에 추가하고 이웃을 탐색
  7. 방문하지 않은 각 이웃에 대해 방문한 것으로 표시하고 대기열에 추가한 다음 계속
  8. 그래프에서 도달 가능한 모든 정점을 방문하면 방문한 정점 목록을 너비 우선 순서로 반환