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