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

Гүнзгийрүүлэх хайлт

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

Гүнзгийрүүлэх хайлт нь граф дахь эх орой $u$-ээс орой бүр хүрэх лексикографын хувьд эхний замыг олно. Гүнзгийрүүлэх хайлт нь модонд хамгийн богино замыг ч бас олно (учир нь зөвхөн нэг энгийн зам оршин байдаг), гэвч ерөнхий графт ийм биш.

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

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

DFS-ийн цаад санаа бол граф руу аль болох гүнзгий орох, зочлоогүй зэргэлдээ оройгүй оройд хүрмэгц буцах явдал юм.

Алгоритмыг рекурсивээр тайлбарлах / хэрэгжүүлэхэд маш амархан: Бид хайлтыг нэг оройноос эхэлнэ. Оройд зочилсны дараа бид өмнө нь зочлоогүй зэргэлдээ орой бүрийн хувьд цааш DFS гүйцэтгэнэ. Ингэснээр бид эхлэлийн оройноос хүрч болох бүх оройд зочилно.

Дэлгэрэнгүйг хэрэгжүүлэлтээс үзнэ үү.

Гүнзгийрүүлэх хайлтын хэрэглээ

  • Граф дахь эх орой $u$-ээс бүх орой хүрэх дурын замыг ол.

  • Граф дахь эх $u$-ээс бүх орой хүрэх лексикографын хувьд эхний замыг ол.

  • Модон дахь орой нь өөр ямар нэг оройн өвөг эсэхийг шалга:

    Хайлтын дуудалт бүрийн эхэн ба төгсгөлд бид орой бүрийн орох ба гарах "хугацаа"-г санана. Одоо та дурын оройн хос $(i, j)$-ийн хувьд хариуг $O(1)$-д олж болно: орой $i$ нь зөвхөн $\text{entry}[i] < \text{entry}[j]$ ба $\text{exit}[i] > \text{exit}[j]$ байх үед л орой $j$-ийн өвөг болно.

  • Хоёр оройн хамгийн бага нийтлэг өвгийг (LCA) ол.

  • Топологийн эрэмбэлэлт:

    Орой бүрд яг нэг удаа $O(n + m)$ хугацаанд зочлохоор цуврал гүнзгийрүүлэх хайлт ажиллуул. Шаардлагатай топологийн эрэмбэ нь гарах хугацааны буурах дарааллаар эрэмбэлэгдсэн оройнууд байна.

  • Өгөгдсөн граф циклгүй эсэхийг шалгаж, граф дахь циклийг ол. (Доор дурдсанчлан холбоост компонент бүрд буцах ирмэгүүдийг тоолох замаар).

  • Чиглэлтэй граф дахь хүчтэй холбоост компонентыг ол:

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

  • Чиглэлгүй граф дахь гүүрийг ол:

    Эхлээд цуврал гүнзгийрүүлэх хайлт ажиллуулж, ирмэг бүрийг дайран өнгөрөх үедээ явсан чиглэлээрээ чиглэлтэй болгож өгөгдсөн графыг чиглэлтэй граф болгон хувирга. Хоёрдугаарт энэ чиглэлтэй граф дахь хүчтэй холбоост компонентыг ол. Гүүр гэдэг нь үзүүрүүд нь өөр өөр хүчтэй холбоост компонентод харьяалагдах ирмэгүүд юм.

Графын ирмэгүүдийн ангилал

Бид граф $G$-ийн ирмэгүүдийг ирмэг $(u,v)$-ийн төгсгөлийн зангилаа $u$ ба $v$-ийн орох ба гарах хугацааг ашиглан ангилж болно. Эдгээр ангиллыг гүүр олох, зангилаа цэг олох зэрэг бодлогод ихэвчлэн ашигладаг.

Бид DFS гүйцэтгэж, тааралдсан ирмэгүүдийг дараах дүрмээр ангилна:

Хэрэв $v$-д зочлоогүй бол:

  • Модны ирмэг — Хэрэв $v$-д $u$-ийн дараа зочилсон бол ирмэг $(u,v)$-г модны ирмэг гэж нэрлэнэ. Өөрөөр хэлбэл хэрэв $v$-д анх удаа зочилж байгаа ба $u$-д одоо зочилж байгаа бол $(u,v)$-г модны ирмэг гэж нэрлэнэ. Эдгээр ирмэг DFS мод үүсгэдэг тул модны ирмэг гэсэн нэртэй.

Хэрэв $v$-д $u$-ээс өмнө зочилсон бол:

  • Буцах ирмэг — Хэрэв $v$ нь $u$-ийн өвөг бол ирмэг $(u,v)$ нь буцах ирмэг юм. $v$ нь бид $v$ рүү аль хэдийн орсон боловч түүнээс хараахан гараагүй байх үед л өвөг байна. Өвөг $v$-ээс удам $u$ хүрэх зам (DFS-ийн рекурсид) ба удам $u$-ээс өвөг $v$ хүрэх ирмэг (буцах ирмэг) байдаг тул буцах ирмэг цикл гүйцээж, ингэснээр цикл үүснэ. Буцах ирмэг ашиглан циклийг илрүүлж болно.

  • Урагшлах ирмэг — Хэрэв $v$ нь $u$-ийн удам бол ирмэг $(u, v)$ нь урагшлах ирмэг юм. Өөрөөр хэлбэл хэрэв бид $v$-д аль хэдийн зочилж, түүнээс гарсан бөгөөд $\text{entry}[u] < \text{entry}[v]$ бол ирмэг $(u,v)$ урагшлах ирмэг үүсгэнэ.

  • Хөндлөн ирмэг: хэрэв $v$ нь $u$-ийн өвөг ч биш, удам ч биш бол ирмэг $(u, v)$ нь хөндлөн ирмэг юм. Өөрөөр хэлбэл хэрэв бид $v$-д аль хэдийн зочилж, түүнээс гарсан бөгөөд $\text{entry}[u] > \text{entry}[v]$ бол $(u,v)$ нь хөндлөн ирмэг юм.

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

$(u,v)$ нь $G$-ийн дурын ирмэг бөгөөд ерөнхий чанараа алдалгүйгээр $u$-д $v$-ээс өмнө зочилсон, өөрөөр хэлбэл $\text{entry}[u] < \text{entry}[v]$ гэж үзье. DFS ирмэгүүдийг зөвхөн нэг удаа боловсруулдаг тул бид ирмэг $(u,v)$-г боловсруулж, улмаар ангилах ердөө хоёр л арга бий:

  • Бид ирмэг $(u,v)$-г анх удаа $u$-ээс $v$ рүү чиглэлд судална. $\text{entry}[u] < \text{entry}[v]$ тул DFS-ийн рекурсив шинж чанар нь бид зангилаа $u$-ээс гарахын тулд "дуудалтын стекээр буцаж дээшлэхээс" өмнө зангилаа $v$ бүрэн судлагдаж, улмаар гарсан байна гэсэн үг. Тиймээс DFS ирмэг $(u,v)$-г $u$-ээс $v$ рүү анх судлах үед зангилаа $v$ зочлоогүй байх ёстой, учир нь эс бөгөөс зангилаа $u$ ба $v$ хөрш тул хайлт зангилаа $v$-ээс гарахаас өмнө $(u,v)$-г $v$-ээс $u$ рүү судалсан байх байсан. Тиймээс ирмэг $(u,v)$ нь модны ирмэг юм.

  • Бид ирмэг $(u,v)$-г анх удаа $v$-ээс $u$ рүү чиглэлд судална. Бид зангилаа $v$-г нээхээс өмнө зангилаа $u$-г нээсэн бөгөөд ирмэгүүдийг зөвхөн нэг удаа боловсруулдаг тул бид ирмэг $(u,v)$-г $v$-ээс $u$ рүү чиглэлд судалж болох цорын ганц арга бол ирмэг $(u,v)$-г хамруулаагүй $u$-ээс $v$ хүрэх өөр зам байх ба ингэснээр $u$ нь $v$-ийн өвөг болох явдал юм. Ингэснээр ирмэг $(u,v)$ нь бидний хараахан гараагүй байгаа удам $v$-ээс өвөг $u$ рүү явж байгаа тул цикл гүйцээнэ. Тиймээс ирмэг $(u,v)$ нь буцах ирмэг юм.

Ирмэг $(u,v)$-г боловсруулах ердөө хоёр л арга байгаа бөгөөд дээр дурдсан хоёр тохиолдол ба тэдгээрийн үр дүнгийн ангилалтай тул $G$ дээр DFS гүйцэтгэхэд тааралдсан ирмэг бүрийг модны ирмэг эсвэл буцах ирмэг гэж ангилна, өөрөөр хэлбэл урагшлах ба хөндлөн ирмэг зөвхөн чиглэлтэй графт оршин байна. Ингэснээр баталгаа дуусав.

Implementation

vector<vector<int>> adj; // graph represented as an adjacency list
int n; // number of vertices

vector<bool> visited;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
}
This is the most simple implementation of Depth First Search. As described in the applications it might be useful to also compute the entry and exit times and vertex color. We will color all vertices with the color 0, if we haven't visited them, with the color 1 if we visited them, and with the color 2, if we already exited the vertex.

Here is a generic implementation that additionally computes those:

vector<vector<int>> adj; // graph represented as an adjacency list
int n; // number of vertices

vector<int> color;

vector<int> time_in, time_out;
int dfs_timer = 0;

void dfs(int v) {
    time_in[v] = dfs_timer++;
    color[v] = 1;
    for (int u : adj[v])
        if (color[u] == 0)
            dfs(u);
    color[v] = 2;
    time_out[v] = dfs_timer++;
}

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