Бодлогоо хараад шууд “DFS хийх үү, BFS хийх үү?” гэж өөрөөсөө асууж байсан уу?
Олон хүн энэ хоёрын ялгааг зөвхөн “гүн” ба “өргөн” гэж ойлгодог. Гэтэл бодит амьдрал дээр бол тэдний зорилго, хэрэглээ, сэтгэлгээний хэв маяг нь өөр.
Энэ нийтлэлээр хоёр хайлтын ялгааг компьютерын шинжлэх ухааны үндсэн логик дээр тулгуурлан, competitive programming-д хэрхэн ашиглахыг жишээтэй нь тайлбарлая.
BFS — Breadth-First Search
“Түвшин-ээс нь эхлэ . Эхлээд ойрхон замуудыг шалга.”
BFS нь хайлтыг түвшин дараалалтайгаар гүйцэтгэдэг. Тодруулбал, эхлэлийн цэгээс эхлээд хамгийн ойрын хөршүүд рүү явж, дараа нь тэдний хөршүүд рүү, гэх мэтээр шаталсан хэлбэрээр тардаг.
BFS нь unweighted (ямар нэгэн жингүй) граф дээр хамгийн богино замыг олох баталгаатай арга юм.
Ашиглах нөхцөл:
- “Хамгийн бага алхамаар хүрэх зам” гэх санааг агуулсан бодлого
- Grid дээр тархалт, ус, гал, халдвар гэх мэт тархах үзэгдэлтэй
Жишээ хэрэглээ:
- Төөрдөг байшингаас хамгийн хурдан гарах зам
- Халдвар хэрхэн тархах вэ гэх мэт
DFS — Depth-First Search
“Гүн рүү ух. Явж болох болтол яв, тэгээд буц.”
DFS нь аль нэг чиглэл рүү гүнзгий явж байгаад цаашаа явах боломжгүй болох үед буцаж, өөр чиглэл рүү ордог. Энэ нь хайлтыг илүү системтэйгээр гүн рүү хийдэг болгодог.
Ашиглах нөхцөл:
- Холбогдсон хэсгийг тоолох
- Бүх замыг шалгах шаардлагатай (backtracking)
- Цикл байгаа эсэх шалгах
BFS vs DFS — Эцсийн шийдвэрийг юу тодорхойлдог вэ?
| Хэрэглээний нөхцөл | Сонгох арга |
|---|---|
| Хамгийн бага алхамтай зам |  BFS (Түвшин) |
| Зүгээр л хүрч чадах эсэх | DFS (Гүн) |
| Grid доторх бүх хэсгийг тоолох | DFS (Гүн) |
| Мод дээрх dynamic programming | DFS (Гүн) |
| Тархалтын загвар (ус, гал, халдвар гэх мэт) | BFS (Түвшин) |
| Бүх боломжит замыг шалгах (Backtracking) | DFS (Гүн) |
Хамгийн чухал санаа:
BFS ба DFS нь аль аль нь O(V + E) хугацаанд ажилладаг ч, тэдний сэтгэлгээний арга барил өөр.
- BFS = “Бүх ойр орчмыг түрүүлж шалга”
- DFS = “Нэг замаар яв, явах газаргүй бол буц”
Гол нь — бодлого чамаас “ямар хайлт” хүсэж байгааг олж харах юм.
Дараагийн нийтлэлээрээ өмнөх нийтлэлүүдээ базаад бодлого бодоцгоое . Byee . Geronimooooooo .
