DFS/BFS|アルゴリズム
10929 ワード
DFS / BFS
1つのノードからグラフィック内のすべてのノードをナビゲート(アクセス)します.
深度優先検索(DFS)
ナビゲーションを開始したノードからブランチの最奥に移動し、次のブランチに移動します.
DFS動作順序
DFS実装
DFS Pythonコード
graph = [
[],
[2, 5, 9],
[1, 3],
[2, 4],
[3],
[1, 6, 8],
[5, 7],
[6],
[5],
[1, 10],
[9]]
visited = [False] * len(graph)
def dfs(graph, vertex, visited):
visited[vertex] = True # 현재 노드 방문 처리
print(vertex, end=' ')
for v in graph[vertex]: # 인접 노드 탐색
if not visited[v]:
dfs(graph, v, visited) # 재귀 호출 (스택)
dfs(graph, 1, visited) # 1 2 3 4 5 6 7 8 9 10Breadth-First Search(BFS)-幅優先ナビゲーション
現在のノードからナビゲートを開始するには:
BFS動作順序
BFSの実装
閲覧を開始するノード(ルートノード)を
BFS Pythonコード
from collections import deque
graph = [
[],
[2, 3, 4],
[1, 5],
[1, 6, 7],
[1, 8],
[2, 9],
[3, 10],
[3],
[4],
[5],
[6]
]
visited = [False] * len(graph)
def bfs(graph, vertex, visited):
queue = deque([vertex])
visited[vertex] = True
while queue: # 큐가 빌 때까지 반복
current_vertex = queue.popleft() # 가장 앞에 있는 노드 제거
print(current_vertex, end=' ')
for v in graph[current_vertex]: # 해당 노드의 인접 노드 검사
if not visited[v]: # 방문하지 않은 인접 노드는 큐에 추가
queue.append(v)
visited[v] = True
bfs(graph, 1, visited) # 1 2 3 4 5 6 7 8 9 10Reference
この問題について(DFS/BFS|アルゴリズム), 我々は、より多くの情報をここで見つけました https://velog.io/@dlskawns96/DFS-BFS-알고리즘-공부テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol