Хамгийн бага тэлэх мод - Крускалын алгоритм¶

Жинтэй чиглэлгүй граф өгөгдсөн. Бид энэ графын бүх оройг холбодог (өөрөөр хэлбэл тэлэх мод болох) ба боломжит бүх тэлэх модны дотроос хамгийн бага жинтэй (өөрөөр хэлбэл бүх ирмэгийн жингийн нийлбэр хамгийн бага байх) дэд модыг олохыг хүсэж байна. Энэ тэлэх модыг хамгийн бага тэлэх мод гэж нэрлэдэг.

Зүүн зурагт жинтэй чиглэлгүй граф, баруун зурагт харгалзах хамгийн бага тэлэх модыг харж болно.

Санамсаргүй граф Энэ графын хамгийн бага тэлэх мод

Энэ өгүүлэлд хамгийн бага тэлэх модтой холбоотой хэдэн чухал баримтыг авч үзээд, дараа нь хамгийн бага тэлэх мод олох Крускалын алгоритмын хамгийн энгийн хэрэгжүүлэлтийг өгнө.

Хамгийн бага тэлэх модны шинж чанарууд¶

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

Крускалын алгоритм¶

Энэ алгоритмыг Жозеф Бернард Крускал Жр. 1956 онд тайлбарласан.

Крускалын алгоритм эхэндээ анхны графын бүх зангилааг бие биенээсээ тусгаарлан байрлуулж, ганц зангилаатай модны ой үүсгэх ба дараа нь эдгээр модыг аажмаар нэгтгэж, итерац бүрд бүх модны дотроос дурын хоёрыг анхны графын ямар нэг ирмэгээр холбоно. Алгоритмыг гүйцэтгэхээс өмнө бүх ирмэгийг жингээр нь (буурахгүй дарааллаар) эрэмбэлнэ. Дараа нь нэгтгэх процесс эхэлнэ: эхнийхээс сүүлчийнх хүртэл бүх ирмэгийг (эрэмбэлэгдсэн дарааллаар) сонгох ба хэрэв одоо сонгосон ирмэгийн үзүүрүүд өөр өөр дэд модонд харьяалагдаж байвал эдгээр дэд модыг нэгтгэж, ирмэгийг хариуд нэмнэ. Бүх ирмэгийг давтан үзсэний дараа бүх орой нэг дэд модонд харьяалагдах ба бид хариугаа авна.

The simplest implementation¶

The following code directly implements the algorithm described above, and is having $O(M \log M + N^2)$ time complexity. Sorting edges requires $O(M \log N)$ (which is the same as $O(M \log M)$) operations. Information regarding the subtree to which a vertex belongs is maintained with the help of an array tree_id[] - for each vertex v, tree_id[v] stores the number of the tree , to which v belongs. For each edge, whether it belongs to the ends of different trees, can be determined in $O(1)$. Finally, the union of the two trees is carried out in $O(N)$ by a simple pass through tree_id[] array. Given that the total number of merge operations is $N-1$, we obtain the asymptotic behavior of $O(M \log N + N^2)$.

struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};

int n;
vector<Edge> edges;

int cost = 0;
vector<int> tree_id(n);
vector<Edge> result;
for (int i = 0; i < n; i++)
    tree_id[i] = i;

sort(edges.begin(), edges.end());

for (Edge e : edges) {
    if (tree_id[e.u] != tree_id[e.v]) {
        cost += e.weight;
        result.push_back(e);

        int old_id = tree_id[e.u], new_id = tree_id[e.v];
        for (int i = 0; i < n; i++) {
            if (tree_id[i] == old_id)
                tree_id[i] = new_id;
        }
    }
}

Зөв байдлын баталгаа¶

Крускалын алгоритм яагаад бидэнд зөв үр дүн өгдөг вэ?

Хэрэв анхны граф холбоост байсан бол үр дүнгийн граф ч мөн холбоост байна. Учир нь эс бөгөөс дор хаяж нэг ирмэгээр холбогдож болох хоёр компонент байх байсан. Гэвч энэ нь боломжгүй, учир нь компонентуудын id өөр өөр тул Крускал эдгээр ирмэгийн нэгийг сонгосон байх байсан. Мөн бид алгоритмд үүнийг шууд хориглодог тул үр дүнгийн граф ямар ч цикл агуулахгүй. Тиймээс алгоритм тэлэх мод үүсгэнэ.

Тэгвэл энэ алгоритм яагаад бидэнд хамгийн бага тэлэх мод өгдөг вэ?

Бид "хэрэв $F$ нь алгоритмын аль ч үе шатанд алгоритмаар сонгогдсон ирмэгүүдийн олонлог бол $F$-ийн бүх ирмэгийг агуулсан MST оршин байна" гэсэн мэдэгдлийг индукц ашиглан харуулж болно.

Мэдэгдэл эхэндээ илэрхий үнэн, хоосон олонлог нь дурын MST-ийн дэд олонлог юм.

Одоо $F$ нь алгоритмын аль нэг үе шатан дахь ямар нэг ирмэгийн олонлог, $T$ нь $F$-ийг агуулсан MST, $e$ нь бидний Крускал ашиглан нэмэхийг хүсэж буй шинэ ирмэг гэж үзье.

Хэрэв $e$ цикл үүсгэвэл бид түүнийг нэмэхгүй тул энэ алхмын дараа мэдэгдэл үнэн хэвээр байна.

$T$ аль хэдийн $e$-г агуулж байгаа тохиолдолд ч энэ алхмын дараа мэдэгдэл үнэн байна.

$T$ ирмэг $e$-г агуулаагүй тохиолдолд $T + e$ нь цикл $C$-г агуулна. Энэ цикл $F$-д байхгүй дор хаяж нэг ирмэг $f$-г агуулна. Ирмэгүүдийн олонлог $T - f + e$ мөн тэлэх мод байх болно. $f$-ийн жин $e$-ийн жингээс бага байж чадахгүйг анзаар, учир нь эс бөгөөс Крускал $f$-г эрт сонгосон байх байсан. Мөн энэ нь илүү их жинтэй байж чадахгүй, учир нь тэгвэл $T - f + e$-ийн нийт жин $T$-ийн нийт жингээс бага болох ба $T$ аль хэдийн MST тул энэ нь боломжгүй. Энэ нь $e$-ийн жин $f$-ийн жинтэй ижил байх ёстой гэсэн үг. Тиймээс $T - f + e$ мөн MST бөгөөд $F + e$-ийн бүх ирмэгийг агуулна. Тэгэхээр энд ч бас алхмын дараа мэдэгдэл биелсэн хэвээр байна.

Энэ нь мэдэгдлийг батална. Энэ нь бүх ирмэгийг давтан үзсэний дараа үр дүнгийн ирмэгийн олонлог холбоост байх ба MST-д агуулагдана, өөрөөр хэлбэл энэ нь аль хэдийн MST байх ёстой гэсэн үг.

Сайжруулсан хэрэгжүүлэлт¶

Бид Огтлолцолгүй олонлогийн нэгдэл (DSU) өгөгдлийн бүтцийг ашиглан Крускалын алгоритмын ойролцоогоор $O(M \log N)$ time complexity-тэй илүү хурдан хэрэгжүүлэлтийг бичиж болно. Энэ өгүүлэлд ийм аргыг дэлгэрэнгүй тайлбарласан.