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

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

Танд $n$ орой, $m$ ирмэгтэй чиглэлтэй граф өгөгдсөн. Та ирмэг бүр бага индекстэй оройноос илүү том индекстэй орой руу хөтлөхөөр оройнуудын эрэмбийг олох ёстой.

Өөрөөр хэлбэл та графын бүх ирмэгээр тодорхойлогдсон эрэмбэд харгалзах оройнуудын сэлгэмэлийг (топологийн эрэмбэ) олохыг хүсэж байна.

Энд өгөгдсөн нэг граф ба түүний топологийн эрэмбэ байна:

чиглэлтэй графын жишээ нэг топологийн эрэмбэ

Топологийн эрэмбэ давтагдашгүй биш байж болно (жишээ нь $a$-ээс $b$ хүртэл, $a$-ээс $c$ хүртэл зам байх боловч $b$-ээс $c$ хүртэл эсвэл $c$-ээс $b$ хүртэл зам байхгүй $a$, $b$, $c$ гэсэн гурван орой байвал). Жишээ граф мөн олон топологийн эрэмбэтэй, хоёр дахь топологийн эрэмбэ нь дараах байдалтай:

хоёр дахь топологийн эрэмбэ

Топологийн эрэмбэ огт оршин байхгүй байж болно. Энэ нь зөвхөн чиглэлтэй граф цикл агуулаагүй үед л оршино. Эс бөгөөс зөрчил үүснэ: хэрэв $a$ ба $b$ оройг агуулсан цикл байвал $a$ нь $b$-ээс бага индекстэй байх ёстой ($a$-ээс $b$-д хүрч болох тул), мөн илүү том индекстэй ч байх ёстой ($b$-ээс $a$-д хүрч болох тул). Энэ өгүүлэлд тайлбарласан алгоритм мөн циклгүй чиглэлтэй граф бүр дор хаяж нэг топологийн эрэмбэ агуулдгийг байгуулалтаар харуулна.

Топологийн эрэмбэлэлт гарч ирдэг түгээмэл бодлого нь дараах байдалтай. Тодорхойгүй утгатай $n$ хувьсагч байна. Зарим хувьсагчийн хувьд тэдгээрийн нэг нь нөгөөгөөсөө бага гэдгийг бид мэднэ. Та эдгээр хязгаарлалт зөрчилдөж байгаа эсэхийг шалгаж, хэрэв үгүй бол хувьсагчдыг өсөх дарааллаар гаргах ёстой (хэрэв хэд хэдэн хариулт боломжтой бол алийг нь ч гаргана уу). Энэ нь яг $n$ оройтой графын топологийн эрэмбийг олох бодлого болохыг анзаарахад амархан.

Алгоритм

Энэ бодлогыг бодохын тулд бид гүнзгийрүүлэх хайлт ашиглана.

Граф циклгүй гэж үзье. Гүнзгийрүүлэх хайлт юу хийдэг вэ?

Ямар нэг орой $v$-ээс эхлэхэд DFS $v$-ээс гарах бүх ирмэгийн дагуу явахыг оролдоно. Энэ нь үзүүр нь аль хэдийн зочилсон ирмэгүүд дээр зогсох ба үлдсэн ирмэгүүдийн дагуу явж, тэдгээрийн үзүүрт рекурсивээр үргэлжлүүлнэ.

Ингэснээр $\text{dfs}(v)$ функцийн дуудлага дуусах үед $v$-ээс хүрч болох бүх оройд хайлт шууд (нэг ирмэгээр) эсвэл шууд бусаар зочилсон байна.

$\text{dfs}(v)$-г дуусгах үед $v$ оройг жагсаалтад залгая. Хүрч болох бүх оройд аль хэдийн зочилсон тул бид $v$-г залгах үед тэдгээр аль хэдийн жагсаалтад байх болно. Үүнийг графын орой бүрийн хувьд нэг буюу хэд хэдэн гүнзгийрүүлэх хайлт ажиллуулан хийе. Граф дахь чиглэлтэй ирмэг $v \rightarrow u$ бүрийн хувьд $u$ нь энэ жагсаалтад $v$-ээс өмнө гарч ирнэ, учир нь $u$-д $v$-ээс хүрч болно. Тиймээс хэрэв бид энэ жагсаалт дахь оройнуудыг зүгээр л $n-1, n-2, \dots, 1, 0$ гэж шошголвол бид графын топологийн эрэмбийг олсон болно. Өөрөөр хэлбэл жагсаалт нь урвуу топологийн эрэмбийг илэрхийлнэ.

Эдгээр тайлбарыг мөн DFS алгоритмын гарах хугацаагаар илэрхийлж болно. Орой $v$-ийн гарах хугацаа гэдэг нь $\text{dfs}(v)$ функцийн дуудлага дууссан хугацаа юм (хугацааг $0$-ээс $n-1$ хүртэл дугаарлаж болно). Дурын орой $v$-ийн гарах хугацаа нь түүнээс хүрч болох дурын оройн гарах хугацаанаас үргэлж их байхыг ойлгоход амархан (учир нь тэдгээрт $\text{dfs}(v)$ дуудлагаас өмнө эсвэл түүний явцад зочилсон). Ингэснээр хайж буй топологийн эрэмбэ нь гарах хугацаагаараа буурах дарааллаар байрлах оройнууд юм.

Implementation

Here is an implementation which assumes that the graph is acyclic, i.e. the desired topological ordering exists. If necessary, you can easily check that the graph is acyclic, as described in the article on depth-first search.

int n; // number of vertices
vector<vector<int>> adj; // adjacency list of graph
vector<bool> visited;
vector<int> ans;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
        }
    }
    ans.push_back(v);
}

void topological_sort() {
    visited.assign(n, false);
    ans.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    reverse(ans.begin(), ans.end());
}

The main function of the solution is topological_sort, which initializes DFS variables, launches DFS and receives the answer in the vector ans. It is worth noting that when the graph is not acyclic, topological_sort result would still be somewhat meaningful in a sense that if a vertex $u$ is reachable from vertex $v$, but not vice versa, the vertex $v$ will always come first in the resulting array. This property of the provided implementation is used in Kosaraju's algorithm to extract strongly connected components and their topological sorting in a directed graph with cycles.

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