← Back to Home
ការស្វែងរកតាមទទឹង (BFS)
ក្បួនដោះស្រាយការឆ្លងកាត់ក្រាហ្វដែលស្វែងរកអ្នកជិតខាងជាមុនសិន មុននឹងផ្លាស់ទីទៅកម្រិតបន្ទាប់នៃអ្នកជិតខាង។
Visualization
Step 1 / 9
Speed:
Details
Analogy
ស្រមៃពីរលកដែលកើតឡើងនៅពេលអ្នកទម្លាក់ថ្មក្នុងស្រះ។ BFS ដូចជាការស្វែងរករលកនោះ។ អ្នកទៅមើលកំពូលដែលថ្ម 'ប៉ះ' ដោយផ្ទាល់ជាមុនសិន (កម្រិត 1) បន្ទាប់មកកំពូលទាំងអស់ដែលតភ្ជាប់ជាមួយពួកវា (កម្រិត 2) ហើយបន្តទៅមុខទៀត ដោយផ្សព្វផ្សាយចេញយ៉ាងសមស្រប។
Purpose
ដើម្បីស្វែងរកក្រាហ្វតាមកម្រិត។ វាត្រូវបានប្រើជាញឹកញាប់ដើម្បីរកផ្លូវខ្លីបំផុតរវាងកំពូលពីរក្នុងក្រាហ្វគ្មានទម្ងន់។
Use Cases
ការរកផ្លូវខ្លីបំផុតក្នុងក្រាហ្វគ្មានទម្ងន់ (ឧទាហរណ៍ ការណែនាំ GPS សម្រាប់ការបត់តិចបំផុត) កម្មវិធីចាប់យកទំព័រវេបដែលធ្វើលិបិក្រម ការរកផ្នែកដែលតភ្ជាប់គ្នាក្នុងក្រាហ្វ និងបណ្តាញ peer-to-peer។
Algorithm Steps
Line 1
1
create queue Q
2
mark start as visited
3
Q.enqueue(start)
4
while Q is not empty:
5
node = Q.dequeue()
6
process node
7
for each neighbor of node:
8
if neighbor not visited:
9
mark neighbor as visited
10
Q.enqueue(neighbor)
Current
Executed
Pending
Explanation
What's Happening?
Step 1/9
ចាប់ផ្តើមនៅកំពូល A។ បន្ថែមវាទៅ queue នៃកំពូលដែលត្រូវទស្សនា។ Queue: [A]
Updates with each step • Clickfor full view
Code Implementation
from collections import deque
def bfs(graph, start_node):
visited = set()
queue = deque([start_node])
visited.add(start_node)
while queue:
current_node = queue.popleft()
print(current_node)
for neighbor in graph[current_node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)