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-р орой гэдэг бол U орой. Мөн энэ замын урт нь нэгээр нэмэгдэнэ cnt++. Тэгээд U оройтой шууд ирмэгээр холбогдсон мөн энэ замд ороогүй оройгоос dfs үргэлжлэх юм. Гэтэл энэ оройтой шууд ирмэгээр холбогдсон бүх орой нь бидний одоо явж буй замд орсон байвал яах вэ? Энэ нь одоо байгаа зам нь цаашаа үргэлжлэх боломжгүй болсон гэсэн үг ба энэ замаас хамгийн сүүлийн оройг хасах хэрэгтэй болно. Бид энэ оройг хэрхэн хасах вэ? энэ нь vis[U] = 0 болгох бөгөөд U орой нь одоо явж байгаа замд U орой нь орохгүй гэсэн утгатай. Нэг орой хасагдаж байгаа гэдэг нь замын урт нэгээр хасагдана cnt--. Ерөнхийдөө бол бид X оройгоос боломжит бүх замаар явж үзэж байгаа. BFS ашиглан энэ бодлогыг бодоорой. Доорх код энэ хаяг дээр байгаа.
Бидэнд нэг граф өгөгдсөн гэж үзье. Мөн 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-р орой гэдэг бол U орой. Мөн энэ замын урт нь нэгээр нэмэгдэнэ cnt++. Тэгээд U оройтой шууд ирмэгээр холбогдсон мөн энэ замд ороогүй оройгоос dfs үргэлжлэх юм. Гэтэл энэ оройтой шууд ирмэгээр холбогдсон бүх орой нь бидний одоо явж буй замд орсон байвал яах вэ? Энэ нь одоо байгаа зам нь цаашаа үргэлжлэх боломжгүй болсон гэсэн үг ба энэ замаас хамгийн сүүлийн оройг хасах хэрэгтэй болно. Бид энэ оройг хэрхэн хасах вэ? энэ нь vis[U] = 0 болгох бөгөөд U орой нь одоо явж байгаа замд U орой нь орохгүй гэсэн утгатай. Нэг орой хасагдаж байгаа гэдэг нь замын урт нэгээр хасагдана cnt--. Ерөнхийдөө бол бид X оройгоос боломжит бүх замаар явж үзэж байгаа. BFS ашиглан энэ бодлогыг бодоорой. Доорх код энэ хаяг дээр байгаа.
- #include <vector>
- #include <iostream>
- using namespace std;
- int cnt; // одоо явж байгаа замын урт
- int n, m; // орой болон ирмэгийн тоо
- int x, y; // хүсэлтийн 2 орой
- int s[20]; // явсан замыг хамдгалах массив
- bool vis[20]; // замд орсон ороогүйг хадгалах массив
- vector<int> adj[20]; // графын мэдээллийг хадгалах вектор
- void dfs(int u) {
- if( u == y ) {
- // одоо ирсэн орой нь бидний очих ёстой оройтой ижил бол
- // бид нэг зам олж чадсан тул үүнийгээ хэвлэнэ
- for(int i = 1; i <= cnt; i++) cout << s[i] << " ";
- cout << y << endl; // сүүлийн оройг хэвлэнэ
- // учир нь бид нэмээгүй байгаа
- return;
- }
- // одоо бид u гэсэн орой дээр ирж байгаа тул
- vis[u] = true; // замд орсон гэж тэмдэглэнэ
- cnt++; // замын урт нэгээр нэмэгдэнэ
- s[cnt] = u; // cnt-р орой гэдэг бол u гэсэн орой байх юм.
- for(int v:adj[u]) {
- if( !vis[v] ) {
- // v гэсэн орой нь энэ замд ордоггүй бол энэ оройгоос
- // цааш явж болох зам байгаа
- dfs(v);
- }
- }
- vis[u] = 0; // энэ оройг ирээгүй болгож тэмдэглэнэ
- cnt--; // замын урт хасагдана
- }
- int main() {
- cin >> n >> m;
- while( m-- ) {
- int u, v; // u, v 2 орой хоорондоо шууд ирмэгээр
- // холбогддог гэсэн үг
- cin >> u >> v;
- adj[u].push_back( v );
- adj[v].push_back( u );
- }
- cin >> x >> y;
- dfs( x );
- return 0;
- }
Comments
Post a Comment