DFS vs BFS: Гүн чухал уу? Өргөн чухал уу?

Бодлогоо хараад шууд “DFS хийх үү, BFS хийх үү?” гэж өөрөөсөө асууж байсан уу?

Олон хүн энэ хоёрын ялгааг зөвхөн “гүн” ба “өргөн” гэж ойлгодог. Гэтэл бодит амьдрал дээр бол тэдний зорилго, хэрэглээ, сэтгэлгээний хэв маяг нь өөр.

Энэ нийтлэлээр хоёр хайлтын ялгааг компьютерын шинжлэх ухааны үндсэн логик дээр тулгуурлан, competitive programming-д хэрхэн ашиглахыг жишээтэй нь тайлбарлая.

BFS — Breadth-First Search

“Түвшин-ээс нь эхлэ . Эхлээд ойрхон замуудыг шалга.”

BFS нь хайлтыг түвшин дараалалтайгаар гүйцэтгэдэг. Тодруулбал, эхлэлийн цэгээс эхлээд хамгийн ойрын хөршүүд рүү явж, дараа нь тэдний хөршүүд рүү, гэх мэтээр шаталсан хэлбэрээр тардаг.

BFS нь unweighted (ямар нэгэн жингүй) граф дээр хамгийн богино замыг олох баталгаатай арга юм.

Ашиглах нөхцөл:

• “Хамгийн бага алхамаар хүрэх зам” гэх санааг агуулсан бодлого

• Grid дээр тархалт, ус, гал, халдвар гэх мэт тархах үзэгдэлтэй

Жишээ хэрэглээ:

• Төөрдөг байшингаас хамгийн хурдан гарах зам

• Халдвар хэрхэн тархах вэ гэх мэт

DFS — Depth-First Search

Гүн рүү ух. Явж болох болтол яв, тэгээд буц

DFS нь аль нэг чиглэл рүү гүнзгий явж байгаад цаашаа явах боломжгүй болох үед буцаж, өөр чиглэл рүү ордог. Энэ нь хайлтыг илүү системтэйгээр гүн рүү хийдэг болгодог.

DFS нь мод бүтэцтэй граф дээр бүтцийн шинжилгээ, DP, цикл (cycle) шалгалт зэрэгт зайлшгүй шаардлагатай.

Ашиглах нөхцөл:

• Холбогдсон хэсгийг тоолох

• Бүх замыг шалгах шаардлагатай (backtracking)

• Цикл байгаа эсэх шалгах

BFS vs DFS — Эцсийн шийдвэрийг юу тодорхойлдог вэ?

Хамгийн чухал санаа:

BFS ба DFS нь аль аль нь O(V + E) хугацаанд ажилладаг ч, тэдний сэтгэлгээний арга барил өөр.

• BFS = “Бүх ойр орчмыг түрүүлж шалга”

• DFS = “Нэг замаар яв, явах газаргүй бол буц”

Гол нь — бодлого чамаас “ямар хайлт” хүсэж байгааг олж харах юм.

Дараагийн нийтлэлээрээ өмнөх нийтлэлүүдээ базаад бодлого бодоцгоое . Byee . Geronimooooooo .

Боловсролыг Инженерчлэв.