[アルゴリズム概念]DFS、深度優先探索、プリアンブル優先探索
DFS (Depth-First Search)
コンセプト
深さ優先ブラウズによるグラフィックの深さの深い部分の優先ブラウズのアルゴリズム
スタック
すべてのノードをグラフィックまたはツリーで参照できます.
ループアルゴリズム(呼び出し自体)なので、ノードにアクセスするかどうかのリストが必要です
def dfs(graph, v, visited):
visited[v] = True
print(v, end = ' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False] * 9
dfs(graph, 1, visited)
DFS : 1 2 7 6 8 3 4 5
BFS (Breadth-First Search)
コンセプト
図面内の最も近いノードを優先的に参照するアルゴリズム
キューの使用
すべてのノードをグラフィックまたはツリーで参照できます.
ループアルゴリズム(呼び出し自体)なので、ノードにアクセスするかどうかのリストが必要です
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue :
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False] * 9
bfs(graph, 1, visited)
BFS : 1 2 3 8 7 4 5 6
[ソース:ツリーウィキ]
https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3
Reference
この問題について([アルゴリズム概念]DFS、深度優先探索、プリアンブル優先探索), 我々は、より多くの情報をここで見つけました https://velog.io/@gandi0330/Python-알고리즘-DFS-BFS-Depth-First-Search-Breadth-First-Searchテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol