DFS/BFS
DFS(Depth-First Search)
深さ優先探索は深さ優先探索とも呼ばれ、スタックデータ構造(または再帰関数)を利用したグラフィックで深さを優先的に探索するアルゴリズムである.具体的な動作過程
1)ナビゲーション開始ノードをスタックに挿入し、アクセスを処理する
2)隣接ノードがスタックの最上位ノードにアクセスしていない場合、そのノードをスタックに入れてアクセス処理を行う.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.
3)完了できないまで2回の処理を繰り返す.
幅優先探索は,グラフィックに近いノード優先探索アルゴリズムとも呼ばれ,キューデータ構造を利用する.
👉 特定の条件の最短パス問題としてもよく用いられる.具体的な動作過程
1)ナビゲーション開始ノードをキューに挿入してアクセス処理を行う.
2)キューからノードを取り出した後,そのノードのすべての隣接ノードにおいてアクセスされていないノードをキューに挿入してアクセス処理を行う.
3)完了できないまで2回の処理を繰り返す.
出典:これが就業コードテストリンクテキスト
深さ優先探索は深さ優先探索とも呼ばれ、スタックデータ構造(または再帰関数)を利用したグラフィックで深さを優先的に探索するアルゴリズムである.
1)ナビゲーション開始ノードをスタックに挿入し、アクセスを処理する
2)隣接ノードがスタックの最上位ノードにアクセスしていない場合、そのノードをスタックに入れてアクセス処理を行う.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.
3)完了できないまで2回の処理を繰り返す.
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]
]
#각 노드가 방문된 정보를 표현
#이 때, 0번째 노드도 false로 표현해주기 위해 총 갯수인 9를 곱해준다.
visited = [False] * 9
#정의된 dfs 함수 호출
dfs(graph, 1, visited)
BFS(Breadth-First Search)幅優先探索は,グラフィックに近いノード優先探索アルゴリズムとも呼ばれ,キューデータ構造を利用する.
👉 特定の条件の最短パス問題としてもよく用いられる.
1)ナビゲーション開始ノードをキューに挿入してアクセス処理を行う.
2)キューからノードを取り出した後,そのノードのすべての隣接ノードにおいてアクセスされていないノードをキューに挿入してアクセス処理を行う.
3)完了できないまで2回の処理を繰り返す.
from collections import deque
#bfs 메서드 정의
def bfs(graph, start, visited):
#큐 구현을 위해 deque 라이브러리 사용
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
#정의된 dfs 함수 호출
bfs(graph, 1, visited)
<クリーンアップ>出典:これが就業コードテストリンクテキスト
Reference
この問題について(DFS/BFS), 我々は、より多くの情報をここで見つけました https://velog.io/@ssongjh55/DFSBFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol