Backtrack-н тухай. Бидэнд нэг граф өгөгдсөн гэж үзье. Мөн X, Y гэсэн хоёр тоо өгөгдөх ба энэ нь X оройгоос Y орой хүрэх бүх боломжит замыг хэвлэ гэсэн бодлого байг. Энэ замд нэг орой нэг л удаа орно. Энэхүү бодлогыг DFS ашиглан бодоцгооё. Эхлээд vis[U] = 1 байвал U гэсэн орой нь одоо явж байгаа замд орсон гэж үзье. Эсрэг тохиолдолд ороогүй. Хэрхэн бид замаа хадгалах вэ? S[] гэсэн массивын эхний элемент гэдэг нь одоо явж байгаа замын эхний орой, дараагийн элемент нь дараагийн орой гэх мэт хадгална. Тэгвэл энэ замд хэдэн орой орсныг хадгалах cnt гэсэн тоог авъя . Эхлээд cnt = 0, vis- ын бүх утга 0 байна. X оройгоос гүний нэвтрэлтээ хийж эхэлье. dfs нь одоо U орой дээр явж байгаа гэж үзье. Хэрвээ энэ орой нь Y оройтой ижил бол бид нэг зам олж чадсан гэсэн үг ба S[1], S[2], ..., S[cnt] хүртэлх бүх оройг хэвлэх ба энэ нь бидний зам. Нэмээд Y оройг хэвлэнэ. Учир нь энэ замд U оройгоо бид нэмээгүй байгаа. Эсрэг тохиолдолд S[cnt+1]=U, vis[U] = 1 болно. Учир нь энэ замын cnt+1-р орой
Алгоритмын хичээл