Breadth-first search (BFS) និង depth-first search (DFS) គឺជាវិធីសាស្ត្រគ្រឹះពីរដើម្បីរុករកគ្រប់ node នៃ graph។ BFS រីកសាយចេញម្តងមួយកម្រិតពី node ចាប់ផ្ដើមដោយប្រើ queue ចំណែក DFS ដើរតាមផ្លូវមួយឱ្យជ្រៅបំផុតតាមដែលអាចធ្វើទៅបានមុនពេលត្រឡប់ក្រោយ (backtracking) ដោយប្រើ stack។ ឧបករណ៍នេះដំណើរការវិធីទាំងពីរលើ graph តែមួយ និងបង្ហាញទិន្នន័យក្នុង queue ឬ stack, លំដាប់នៃការទៅដល់ និង edges ដែលប្រើដើម្បីទៅដល់ node នីមួយៗ។
អ្នកអាចកែសម្រួល graph បានតាមចិត្ត៖ បន្ថែម node, ភ្ជាប់ ឬផ្ដាច់ខ្សែ, លុប node ឬបង្កើត graph ចៃដន្យ។ បន្ទាប់មកជ្រើសរើស node ចាប់ផ្ដើម រួចចុច Run។ ចុចទៅមុខថយក្រោយដើម្បីមើលឱ្យច្បាស់ពីមូលហេតុដែល BFS រកឃើញផ្លូវខ្លីបំផុតក្នុង unweighted graph ឯ DFS មិនអាចធ្វើបាន។
របៀបប្រើឧបករណ៍ ឧបករណ៍បង្ហាញ Graph តាម BFS និង DFS
- ជ្រើសរើស BFS ឬ DFS និង node ចាប់ផ្តើម (ឬចុចលើ node ក្នុងម៉ូដ Pick start)។
- កែសម្រួល graph តាមតម្រូវការ៖ Add node (ចុចលើកន្លែងទំនេរ), Add or remove edge (ចុចលើ node ពីរ) ឬ Delete node។
- ចុច Run ហើយតាមដាន៖ node ពណ៌ទឹកក្រូចកំពុងត្រូវបានរុករក, node ពណ៌ស្វាយកំពុងរង់ចាំក្នុង queue ឬ stack, node ពណ៌បៃតងគឺរួចរាល់។
- ពិនិត្យមើល queue ឬ stack និងលំដាប់នៃការទៅដល់នៅខាងក្រោម graph ព្រមទាំងបន្ទាត់ pseudocode ដែលបានបន្លិច។
ហេតុអ្វីប្រើ ឧបករណ៍បង្ហាញ Graph តាម BFS និង DFS របស់ ToolOrca
- BFS ជាមួយ queue និង DFS ជាមួយ stack
- Graph អាចកែសម្រួលបាន៖ បន្ថែម និងលុប nodes ព្រមទាំង edges
- Graph គំរូ និង graph បែបចៃដន្យ
- បង្ហាញទិន្នន័យក្នុង queue ឬ stack និងលំដាប់ឆ្លងកាត់នៅគ្រប់ជំហាន
- បន្លិច edges នៃដើមឈើ BFS ឬ DFS យ៉ាងច្បាស់
- កូដជាភាសា C++, Java, Python និង JavaScript
របៀបដែល breadth-first search ដំណើរការ
BFS ដាក់ node ចាប់ផ្ដើមទៅក្នុង queue ហើយសម្គាល់ថាបានឃើញ។ បន្ទាប់មកវាធ្វើឡើងវិញនូវជំហាន៖ ដក node នៅខាងមុខ queue ចេញ ចូលទៅកាន់វា ហើយបន្ថែមរាល់ node ជិតខាងដែលមិនទាន់បានឃើញទៅកាន់ខាងក្រោយ queue។ ដោយសារ queue ដំណើរការតាមបែប ចូលមុនចេញមុន (FIFO) នោះ nodes ទាំងអស់នៅចម្ងាយ 1 នឹងត្រូវឆ្លងកាត់មុន nodes នៅចម្ងាយ 2 ហើយបន្តបន្ទាប់ទៀត។
លំដាប់លំដោយតាមកម្រិតនេះមានន័យថា BFS tree ផ្ដល់នូវ ផ្លូវខ្លីបំផុត (ចំនួន edge តិចបំផុត) ពីចំណុចចាប់ផ្ដើមទៅកាន់គ្រប់ node ដែលអាចទៅដល់បានក្នុង unweighted graph។ BFS ត្រូវបានប្រើសម្រាប់ស្វែងរកផ្លូវខ្លីបំផុតក្នុង grid និង maze, ស្វែងរកមនុស្សក្នុងរង្វង់តភ្ជាប់កម្រិត k ក្នុងបណ្ដាញសង្គម និងសម្រាប់ web crawler។
របៀបដែល depth-first search ដំណើរការ
DFS ប្រើប្រាស់ stack (ឬ recursion ដែលប្រើ call stack)។ Pop យក node មួយចេញ បើរួចរាល់ហើយត្រូវរំលងវា បើមិនទាន់ទេត្រូវចូលទៅកាន់វា ហើយ push nodes ជិតខាងដែលមិនទាន់បានឆ្លងកាត់ចូលទៅក្នុង stack។ Node ដែលទើបតែរកឃើញថ្មីបំផុតនឹងត្រូវរុករកមុនគេ ដូច្នេះ DFS នឹងមុជជ្រៅតាមមែកមួយរហូតដល់ទាល់ផ្លូវ ទើបវាត្រឡប់ថយក្រោយ (backtrack) វិញ។
DFS គឺជាមូលដ្ឋានគ្រឹះសម្រាប់ cycle detection, topological sorting, ការស្វែងរក connected components, ការដោះស្រាយល្បែងប្រាជ្ញា និង maze ដោយប្រើ backtracking ព្រមទាំងការស្វែងរក bridge និង articulation point។ វាប្រើប្រាស់ memory តិចជាង BFS លើ graph ដែលមានទំហំធំទូលាយ ប៉ុន្តែវាមិនអាចរកផ្លូវខ្លីបំផុតបានឡើយ។
Complexity នៃ BFS និង DFS
ជាមួយ adjacency list វិធីទាំងពីរចូលទៅកាន់គ្រប់ vertex ម្តង និងពិនិត្យគ្រប់ edge ម្តង (ពីរដងក្នុង undirected graph) ដូច្នេះដំណើរការទាំងមូលចំណាយពេល O(V + E) ជាមួយ memory បន្ថែម O(V) សម្រាប់ visited set និង queue ឬ stack។ បើប្រើ adjacency matrix វិញ ការស្វែងរក node ជិតខាងចំណាយពេល O(V) ក្នុងមួយ node ដូច្នេះវិធីទាំងពីរនឹងក្លាយជា O(V²)។
គ្រប់ visualizer នៅលើគេហទំព័រនេះដំណើរការផ្ទាល់ក្នុង browser របស់អ្នកជាមួយប៊ូតុងបញ្ជាដូចគ្នា៖ ចាក់ (Play), ផ្អាក (Pause), ទៅមុខមួយជំហាន, ថយក្រោយមួយជំហាន និងរបារលៃល្បឿន។ អ្នកក៏អាចអូសរបារកំណត់ទីតាំងដើម្បីលោតទៅជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូរហើយប្រើប្រាស់ Space bar និងគ្រាប់ចុចព្រួញបានផងដែរ។
សំណួរដែលសួរញឹកញាប់
តើ BFS និង DFS ខុសគ្នាដូចម្តេច?
BFS រុករក node ជិតខាងម្តងមួយកម្រិតដោយប្រើ queue រីឯ DFS ដើរឱ្យជ្រៅបំផុតតាមផ្លូវមួយដោយប្រើ stack រួចទើបត្រឡប់ក្រោយវិញ។ BFS ស្វែងរកផ្លូវខ្លីបំផុតក្នុង unweighted graph ចំណែក DFS ល្អបំផុតសម្រាប់ cycle detection, topological sort និង backtracking។
ហេតុអ្វីបានជា BFS អាចរកផ្លូវខ្លីបំផុតឃើញ?
Queue របស់វាដំណើរការ nodes ទាំងអស់នៅចម្ងាយ d មុន nodes នៅចម្ងាយ d + 1 ជានិច្ច ដូច្នេះការទៅដល់ node មួយលើកដំបូងតែងតែជាផ្លូវដែលមានចំនួន edge តិចបំផុត។
តើ Time Complexity នៃ BFS និង DFS ស្មើប៉ុន្មាន?
O(V + E) ជាមួយ adjacency list ដែល V ជាចំនួន vertices និង E ជាចំនួន edges។
តើអាចសរសេរ DFS ដោយមិនប្រើ recursion បានទេ?
បាន។ គ្រាន់តែជំនួស call stack ដោយ explicit stack ផ្ទាល់ខ្លួន ដូចដែល visualizer នេះបានធ្វើ។ ការ push nodes ជិតខាងតាមលំដាប់បញ្ច្រាស នឹងធ្វើឱ្យវាដំណើរការតាមលំដាប់ដូចគ្នាទៅនឹង recursive version ដែរ។
តើមានអ្វីកើតឡើងចំពោះ nodes ដែលមិនអាចទៅដល់?
ពួកវានឹងមិនត្រូវបានឆ្លងកាត់ឡើយ។ អ្នកអាចដំណើរការ BFS ឬ DFS ម្តងទៀតចេញពី node ដែលមិនទាន់បានឆ្លងកាត់ ដើម្បីស្វែងរក connected component នីមួយៗ។