Агуулгыг алгасах

Өргөнөөр эхлэх хайлт

Өргөнөөр эхлэх хайлт бол граф дээрх үндсэн бөгөөд чухал хайлтын алгоритмуудын нэг юм.

Алгоритмын ажиллах зарчмын үр дүнд өргөнөөр эхлэх хайлтаар дурын зангилаа хүртэл олдсон зам нь тэр зангилаа хүрэх хамгийн богино зам, өөрөөр хэлбэл жингүй графт хамгийн цөөн ирмэг агуулсан зам байна.

Алгоритм $O(n + m)$ хугацаанд ажиллана, энд $n$ нь оройн тоо, $m$ нь ирмэгийн тоо юм.

Алгоритмын тайлбар

Алгоритм оролт болгон жингүй граф ба эх орой $s$-ийн id-г авна. Оролтын граф чиглэлтэй эсвэл чиглэлгүй байж болох ба энэ нь алгоритмд хамаагүй.

Алгоритмыг граф дээр тархаж буй гал гэж ойлгож болно: тэгдүгээр алхамд зөвхөн эх $s$ шатаж байна. Алхам бүрд орой бүрд шатаж буй гал түүний бүх хөрш рүү тархана. Алгоритмын нэг итерацад "галын цагираг" өргөнөөрөө нэг нэгжээр тэлнэ (эндээс алгоритмын нэр гарсан).

Илүү нарийвчлан алгоритмыг дараах байдлаар томьёолж болно: боловсруулах оройнуудыг агуулах дараалал $q$, мөн орой бүрийн хувьд түүнийг асаасан (эсвэл зочилсон) эсэхийг заах Булын массив $used[]$ үүсгэ.

Эхэндээ эх $s$-г дараалалд түлхэж, $used[s] = true$ гэж тохируулаад бусад бүх орой $v$-ийн хувьд $used[v] = false$ гэж тохируул. Дараа нь дараалал хоосон болтол давтаж, итерац бүрд дарааллын эхнээс нэг оройг гарга. Энэ оройноос гарах бүх ирмэгийг давтан үзэж, хэрэв эдгээр ирмэгийн зарим нь аль хэдийн асаагүй орой руу очиж байвал тэдгээрийг асааж, дараалалд байрлуул.

Үр дүнд нь дараалал хоосон болоход "галын цагираг" нь эх $s$-ээс хүрч болох бүх оройг агуулах ба орой бүрд боломжит хамгийн богино замаар хүрсэн байна. Та мөн хамгийн богино замын уртыг тооцоолж болно (үүнд ердөө замын уртын массив $d[]$ хөтлөх шаардлагатай), мөн эдгээр бүх хамгийн богино замыг сэргээх мэдээллийг хадгалж болно (үүний тулд орой бүрийн хувьд бид түүнд хүрч ирсэн оройг хадгалдаг "эцгүүд"-ийн массив $p[]$ хөтлөх шаардлагатай).

Implementation

We write code for the described algorithm in C++ and Java.

vector<vector<int>> adj;  // adjacency list representation
int n; // number of nodes
int s; // source vertex

queue<int> q;
vector<bool> used(n);
vector<int> d(n), p(n);

q.push(s);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : adj[v]) {
        if (!used[u]) {
            used[u] = true;
            q.push(u);
            d[u] = d[v] + 1;
            p[u] = v;
        }
    }
}

ArrayList<ArrayList<Integer>> adj = new ArrayList<>(); // adjacency list representation

int n; // number of nodes
int s; // source vertex


LinkedList<Integer> q = new LinkedList<Integer>();
boolean used[] = new boolean[n];
int d[] = new int[n];
int p[] = new int[n];

q.push(s);
used[s] = true;
p[s] = -1;
while (!q.isEmpty()) {
    int v = q.pop();
    for (int u : adj.get(v)) {
        if (!used[u]) {
            used[u] = true;
            q.push(u);
            d[u] = d[v] + 1;
            p[u] = v;
        }
    }
}

If we have to restore and display the shortest path from the source to some vertex $u$, it can be done in the following manner:

if (!used[u]) {
    cout << "No path!";
} else {
    vector<int> path;
    for (int v = u; v != -1; v = p[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    cout << "Path: ";
    for (int v : path)
        cout << v << " ";
}

if (!used[u]) {
    System.out.println("No path!");
} else {
    ArrayList<Integer> path = new ArrayList<Integer>();
    for (int v = u; v != -1; v = p[v])
        path.add(v);
    Collections.reverse(path);
    for(int v : path)
        System.out.println(v);
}

BFS-ийн хэрэглээ

  • Жингүй граф дахь эхээс бусад орой хүрэх хамгийн богино замыг ол.

  • Чиглэлгүй граф дахь бүх холбоост компонентыг $O(n + m)$ хугацаанд ол: Үүний тулд бид өмнөх ажиллуулалтад аль хэдийн зочилсон оройнуудаас бусад орой бүрээс эхлэн BFS ажиллуулна. Ингэснээр бид оройнууд тус бүрээс ердийн BFS гүйцэтгэх боловч шинэ холбоост компонент авах бүрд $used[]$ массивыг тэглэхгүй бөгөөд нийт ажиллах хугацаа $O(n + m)$ хэвээр байна ($used []$ массивыг тэглэхгүйгээр граф дээр олон BFS гүйцэтгэхийг цуврал өргөнөөр эхлэх хайлт гэж нэрлэдэг).

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

  • Жин нь 0 эсвэл 1 байх граф дахь хамгийн богино замыг олох: Үүнд ердийн өргөнөөр эхлэх хайлтад ердөө бага зэргийн өөрчлөлт хэрэгтэй: $used[]$ массив хөтлөхийн оронд бид одоо орой хүрэх зай одоогийн олдсон зайнаас богино эсэхийг шалгаж, дараа нь хэрэв одоогийн ирмэг тэг жинтэй бол түүнийг дарааллын эхэнд, эс бөгөөс дарааллын төгсгөлд нэмнэ. Энэ өөрчлөлтийг 0-1 BFS өгүүлэлд илүү дэлгэрэнгүй тайлбарласан.

  • Чиглэлтэй жингүй граф дахь хамгийн богино циклийг олох: Орой бүрээс өргөнөөр эхлэх хайлт эхлүүл. Бид одоогийн оройноос эх орой руу буцаж очихыг оролдмогц эх оройг агуулсан хамгийн богино циклийг оллоо гэсэн үг. Энэ үед бид BFS-г зогсоож, дараагийн оройноос шинэ BFS эхлүүлж болно. Ийм бүх циклээс (BFS тус бүрээс хамгийн ихдээ нэг) хамгийн богиныг нь сонго.

  • Өгөгдсөн оройн хос $(a, b)$-ийн хоорондох дурын хамгийн богино зам дээр орших бүх ирмэгийг ол. Үүний тулд хоёр өргөнөөр эхлэх хайлт ажиллуул: нэгийг $a$-ээс, нөгөөг $b$-ээс. $d_a []$ нь эхний BFS-ээс ($a$-ээс) олж авсан хамгийн богино зайг агуулах массив, $d_b []$ нь $b$-ээс хийсэн хоёр дахь BFS-ээс олж авсан хамгийн богино зайг агуулах массив байг. Одоо ирмэг $(u, v)$ бүрийн хувьд тэр ирмэг $a$ ба $b$-ийн хоорондох дурын хамгийн богино зам дээр орших эсэхийг шалгахад амархан: шалгуур нь $d_a [u] + 1 + d_b [v] = d_a [b]$ нөхцөл юм.

  • Өгөгдсөн оройн хос $(a, b)$-ийн хоорондох дурын хамгийн богино зам дээрх бүх оройг ол. Үүнийг хийхийн тулд хоёр өргөнөөр эхлэх хайлт ажиллуул: нэгийг $a$-ээс, нөгөөг $b$-ээс. $d_a []$ нь эхний BFS-ээс ($a$-ээс) олж авсан хамгийн богино зайг агуулах массив, $d_b []$ нь хоёр дахь BFS-ээс ($b$-ээс) олж авсан хамгийн богино зайг агуулах массив байг. Одоо орой бүрийн хувьд тэр нь $a$ ба $b$-ийн хоорондох дурын хамгийн богино зам дээр орших эсэхийг шалгахад амархан: шалгуур нь $d_a [v] + d_b [v] = d_a [b]$ нөхцөл юм.

  • Жингүй граф дахь эх орой $s$-ээс зорилтот орой $t$ хүрэх тэгш урттай хамгийн богино явалтыг ол: Үүний тулд бид оройнууд нь төлөв $(v, c)$ байх туслах граф байгуулах ёстой, энд $v$ нь одоогийн зангилаа, $c = 0$ эсвэл $c = 1$ нь одоогийн тэгш сондгой байдал юм. Анхны графын дурын ирмэг $(u, v)$ энэ шинэ графт хоёр ирмэг $((u, 0), (v, 1))$ ба $((u, 1), (v, 0))$ болж хувирна. Үүний дараа бид эхлэлийн орой $(s, 0)$-ээс төгсгөлийн орой $(t, 0)$ хүрэх хамгийн богино явалтыг олохын тулд BFS ажиллуулна.
    Тэмдэглэл: Энэ зүйлд "зам"-ын оронд "явалт" гэсэн нэр томьёог шалтгаантайгаар ашигласан, учир нь олдсон явалтын уртыг тэгш болгохын тулд оройнууд давтагдах магадлалтай. Тэгш урттай хамгийн богино зам олох бодлого нь чиглэлтэй графт NP-бүрэн бөгөөд чиглэлгүй графт шугаман хугацаанд бодогдох боловч хамаагүй илүү нарийн төвөгтэй аргаар.

Дасгал бодлогууд