← Back to Home
ការស្វែងរកតាមជម្រៅ (DFS)
ក្បួនដោះស្រាយការឆ្លងកាត់ក្រាហ្វដែលស្វែងរកឆ្ងាយតាមដែលអាចធ្វើទៅបានតាមសាខានីមួយៗមុននឹងត្រឡប់ក្រោយ។
Visualization
Step 1 / 11
Speed:
Details
Analogy
ស្រមៃការស្វែងរកផ្លូវក្នុងក្រឡាប្រសាទ។ DFS ដូចជាការយកផ្លូវមួយ និងតាមវាទៅដល់ចុងបញ្ចប់។ ប្រសិនបើអ្នកជួបផ្លូវស្លាប់ អ្នកត្រឡប់ក្រោយទៅផ្លូវបត់ចុងក្រោយ ហើយព្យាយាមផ្លូវផ្សេងដែលអ្នកមិនទាន់បានយក។ អ្នកធ្វើឡើងវិញរហូតដល់អ្នកបានស្វែងរកក្រឡាប្រសាទទាំងមូល។
Purpose
ដើម្បីស្វែងរកក្រាហ្វដោយការចុះជម្រៅទៅក្នុងសាខាមួយមុននឹងស្វែងរកសាខាជាបងប្អូនរបស់វា។ វាប្រើ stack (ជាញឹកញាប់តាមរយៈការហៅឡើងវិញ) ដើម្បីតាមដានកំពូលដែលត្រូវទស្សនា។
Use Cases
ការរកឃើញវដ្តក្នុងក្រាហ្វ ការរកផ្លូវ (ឧទាហរណ៍ ក្នុងក្រឡាប្រសាទ) ការរៀបតាមលំដាប់ topological និងការដោះស្រាយល្បែងដូចជា Sudoku។
Algorithm Steps
Line 1
1
function DFS(node, visited):
2
mark node as visited
3
process node
4
for each neighbor of node:
5
if neighbor not visited:
6
DFS(neighbor, visited)
Current
Executed
Pending
Explanation
What's Happening?
Step 1/11
ចាប់ផ្តើមនៅកំពូល A។ សម្គាល់វាថាកំពុងទស្សនា និងដំណើរការវា។
Updates with each step • Clickfor full view
Code Implementation
def dfs(graph, start_node, visited=None):
if visited is None:
visited = set()
visited.add(start_node)
print(start_node)
for neighbor in graph[start_node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)