2.2 ການຄົ້ນຫາແບບກວ້າງ (BFS) ແລະ ແບບເລິກ (DFS)

ສອງວິທີຄົ້ນຫາແບບບອດ: ແຖວຄອຍ (queue) ທຽບກັບ ກອງ (stack).

ການຄົ້ນຫາແບບກວ້າງກ່ອນ (Breadth-First Search – BFS)

ແນວຄິດ: ຂະຫຍາຍຈາກຮາກ → ຂະຫຍາຍທຸກລູກຂອງຮາກ → ຫຼານ ... ທີລະ ຊັ້ນ ຈົນພົບເປົ້າໝາຍ.

Procedure BFS;
1. L ← [ສະຖານະເລີ່ມຕົ້ນ]
2. Loop:
   2.1 ຖ້າ L ຫວ່າງ → ລົ້ມເຫຼວ; ຢຸດ
   2.2 ເອົາ u ອອກຈາກ "ຫົວ" ຂອງ L
   2.3 ຖ້າ u ເປັນເປົ້າໝາຍ → ສຳເລັດ; ຢຸດ
   2.4 ສຳລັບທຸກ v ທີ່ຕິດກັບ u: ໃສ່ v ໄວ້ "ທ້າຍ" L; father(v) ← u

ປະເມີນ: L ເຮັດວຽກຄື ແຖວຄອຍ (queue). - ຖ້າມີຄຳຕອບ → ພົບແນ່ນອນ ແລະ ເປັນ ເສັ້ນທາງສັ້ນທີ່ສຸດ (ຕາມຈຳນວນກ້າວ). - ຖ້າບໍ່ມີຄຳຕອບ ແລະ ພື້ນທີ່ຈຳກັດ → ຢຸດ ແລະ ແຈ້ງວ່າບໍ່ມີຄຳຕອບ. - ຄວາມຊັບຊ້ອນ O(b^d) (b = ຈຳນວນກິ່ງ, d = ຄວາມຍາວຄຳຕອບ).

ການຄົ້ນຫາແບບເລິກກ່ອນ (Depth-First Search – DFS)

ແນວຄິດ: ລົງເລິກໄປທາງໜຶ່ງໃຫ້ສຸດ; ຖ້າຕັນ (ບໍ່ແມ່ນເປົ້າໝາຍ ແລະ ຂະຫຍາຍຕໍ່ບໍ່ໄດ້) ຈຶ່ງຖອຍກັບ.

ຄືກັບ BFS ຍົກເວັ້ນຂັ້ນ 2.4: ໃສ່ v ໄວ້ "ຫົວ" ຂອງ L → L ເຮັດວຽກຄື ກອງ (stack).

ປະເມີນ: - ພື້ນທີ່ຈຳກັດ → ພົບຄຳຕອບ; ພື້ນທີ່ບໍ່ຈຳກັດ → ອາດບໍ່ພົບ (ບໍ່ຄວນໃຊ້ກັບຕົ້ນໄມ້ທີ່ມີກິ່ງບໍ່ສິ້ນສຸດ). - ເວລາ O(b^d) ໃນກໍລະນີຮ້າຍສຸດ, ແຕ່ ໜ່ວຍຄວາມຈຳພຽງ O(d·b) — ປະຢັດກວ່າ BFS ຫຼາຍ.

ສົມທຽບ

🧪 ລອງໃນ ຫ້ອງທົດລອງ: ແຕ້ມກຳແພງ ແລ້ວປຽບທຽບວ່າ BFS ແລະ DFS ສຳຫຼວດຕາລາງແນວໃດ.

🧪 ເປີດຫ້ອງທົດລອງສຳລັບບົດນີ້