Хамгийн бага тэлэх мод - Примийн алгоритм¶
$n$ орой, $m$ ирмэгтэй жинтэй чиглэлгүй граф $G$ өгөгдсөн. Та энэ графын бүх оройг холбодог, хамгийн бага жинтэй (өөрөөр хэлбэл ирмэгүүдийн жингийн нийлбэр хамгийн бага байх) тэлэх модыг олохыг хүсэж байна. Тэлэх мод гэдэг нь дурын орой нөгөө дурын оройд яг нэг энгийн замаар хүрч болохоор ирмэгүүдийн олонлог юм. Хамгийн бага жинтэй тэлэх модыг хамгийн бага тэлэх мод гэж нэрлэдэг.
Зүүн зурагт жинтэй чиглэлгүй граф, баруун зурагт харгалзах хамгийн бага тэлэх модыг харж болно.
Дурын тэлэх мод заавал $n-1$ ирмэг агуулна гэдгийг харахад амархан.
Энэ бодлого олон бодлогод нэлээд байгалийн жамаараа гарч ирдэг. Жишээ нь дараах бодлогод: $n$ хот байх ба хотын хос бүрийн хувьд тэдгээрийн хооронд зам барих өртөг өгөгдсөн (эсвэл тэдгээрийн хооронд зам барих нь биет байдлаар боломжгүй гэдгийг бид мэднэ). Бид хот бүрээс бусад хот бүр рүү очиж болохоор, мөн бүх замыг барих өртөг хамгийн бага байхаар замуудыг барих ёстой.
Примийн алгоритм¶
Энэ алгоритмыг анх Чех математикч Войтех Ярник 1930 онд нээсэн. Гэвч энэ алгоритмыг 1957 онд дахин нээж, дахин нийтэлсэн Америк математикч Роберт Клэй Примийн нэрээр Примийн алгоритм гэж голчлон мэддэг. Түүнчлэн Эдсгер Дейкстра энэ алгоритмыг 1959 онд нийтэлсэн.
Алгоритмын тайлбар¶
Энд бид алгоритмыг хамгийн энгийн хэлбэрээр нь тайлбарлана. Хамгийн бага тэлэх модыг ирмэгүүдийг нэг нэгээр нь нэмэх замаар аажмаар байгуулна. Эхэндээ тэлэх мод зөвхөн ганц оройноос (дурмаар сонгосон) тогтоно. Дараа нь энэ оройноос гарах хамгийн бага жинтэй ирмэгийг сонгож, тэлэх модонд нэмнэ. Үүний дараа тэлэх мод аль хэдийн хоёр оройноос тогтоно. Одоо нэг үзүүр нь аль хэдийн сонгогдсон оройд (өөрөөр хэлбэл тэлэх модны аль хэдийн хэсэг болсон оройд), нөгөө үзүүр нь сонгогдоогүй оройд байх хамгийн бага жинтэй ирмэгийг сонгож нэм. Ингэсээр цаашид, өөрөөр хэлбэл бид тухай бүр сонгогдсон нэг оройг сонгогдоогүй нэг оройтой холбох хамгийн бага жинтэй ирмэгийг сонгож нэмнэ. Тэлэх мод бүх оройг агуулах хүртэл (эсвэл түүнтэй эквивалентээр бидэнд $n - 1$ ирмэг болтол) процессыг давтана.
Эцэст нь байгуулагдсан тэлэх мод хамгийн бага байх болно. Хэрэв граф анхнаасаа холбоост биш байсан бол тэлэх мод оршихгүй тул сонгогдсон ирмэгийн тоо $n - 1$-ээс бага байна.
Баталгаа¶
Граф $G$ холбоост байг, өөрөөр хэлбэл хариу оршин байна. Примийн алгоритмаар олдсон үр дүнгийн графыг $T$, хамгийн бага тэлэх модыг $S$ гэж тэмдэглэе. $T$ нь үнэхээр тэлэх мод бөгөөд $G$-ийн дэд граф болох нь илэрхий. Бид зөвхөн $S$ ба $T$-ийн жин давхцаж байгааг харуулах л хэрэгтэй.
Алгоритмд бид $S$-ийн хэсэг биш ирмэгийг $T$-д нэмж буй анхны тохиолдлыг авч үзье. Энэ ирмэгийг $e$, түүний үзүүрүүдийг $a$ ба $b$, аль хэдийн сонгогдсон оройнуудын олонлогийг $V$ гэж тэмдэглэе ($a \in V$ ба $b \notin V$, эсвэл эсрэгээр).
Хамгийн бага тэлэх мод $S$-д орой $a$ ба $b$ ямар нэг зам $P$-ээр холбогдсон байна. Энэ зам дээр бид $f$-ийн нэг үзүүр $V$-д орших, нөгөө үзүүр нь оршихгүй байх ирмэг $f$-г олж чадна. Алгоритм $f$-ийн оронд $e$-г сонгосон тул энэ нь $f$-ийн жин $e$-ийн жингээс их буюу тэнцүү гэсэн үг.
Бид ирмэг $e$-г хамгийн бага тэлэх мод $S$-д нэмж, ирмэг $f$-г хасна. $e$-г нэмснээр бид цикл үүсгэсэн бөгөөд $f$ нь мөн тэр цорын ганц циклийн хэсэг байсан тул түүнийг хассанаар үр дүнгийн граф дахин циклгүй болно. Мөн бид зөвхөн циклээс ирмэг хассан тул үр дүнгийн граф холбоост хэвээр байна.
Үр дүнгийн тэлэх мод илүү их нийт жинтэй байж чадахгүй, учир нь $e$-ийн жин $f$-ийн жингээс их байгаагүй, мөн $S$ нь хамгийн бага тэлэх мод байсан тул илүү бага жинтэй ч байж чадахгүй. Энэ нь ирмэг $f$-г $e$-ээр солисноор бид өөр нэг хамгийн бага тэлэх мод үүсгэсэн гэсэн үг. Мөн $e$ нь $f$-тэй ижил жинтэй байх ёстой.
Ингэснээр Примийн алгоритмд бидний сонгосон бүх ирмэг дурын хамгийн бага тэлэх модны ирмэгүүдтэй ижил жинтэй байх ба энэ нь Примийн алгоритм үнэхээр хамгийн бага тэлэх мод үүсгэдэг гэсэн үг.
Implementation¶
The complexity of the algorithm depends on how we search for the next minimal edge among the appropriate edges. There are multiple approaches leading to different complexities and different implementations.
Trivial implementations: $O(n m)$ and $O(n^2 + m \log n)$¶
If we search the edge by iterating over all possible edges, then it takes $O(m)$ time to find the edge with the minimal weight. The total complexity will be $O(n m)$. In the worst case this is $O(n^3)$, really slow.
This algorithm can be improved if we only look at one edge from each already selected vertex. For example we can sort the edges from each vertex in ascending order of their weights, and store a pointer to the first valid edge (i.e. an edge that goes to an non-selected vertex). Then after finding and selecting the minimal edge, we update the pointers. This give a complexity of $O(n^2 + m)$, and for sorting the edges an additional $O(m \log n)$, which gives the complexity $O(n^2 \log n)$ in the worst case.
Below we consider two slightly different algorithms, one for dense and one for sparse graphs, both with a better complexity.
Dense graphs: $O(n^2)$¶
We approach this problem from a different angle: for every not yet selected vertex we will store the minimum edge to an already selected vertex.
Then during a step we only have to look at these minimum weight edges, which will have a complexity of $O(n)$.
After adding an edge some minimum edge pointers have to be recalculated. Note that the weights only can decrease, i.e. the minimal weight edge of every not yet selected vertex might stay the same, or it will be updated by an edge to the newly selected vertex. Therefore this phase can also be done in $O(n)$.
Thus we received a version of Prim's algorithm with the complexity $O(n^2)$.
In particular this implementation is very convenient for the Euclidean Minimum Spanning Tree problem: we have $n$ points on a plane and the distance between each pair of points is the Euclidean distance between them, and we want to find a minimum spanning tree for this complete graph. This task can be solved by the described algorithm in $O(n^2)$ time and $O(n)$ memory, which is not possible with Kruskal's algorithm.
int n;
vector<vector<int>> adj; // adjacency matrix of graph
const int INF = 1000000000; // weight INF means there is no edge
struct Edge {
int w = INF, to = -1;
};
void prim() {
int total_weight = 0;
vector<bool> selected(n, false);
vector<Edge> min_e(n);
min_e[0].w = 0;
for (int i=0; i<n; ++i) {
int v = -1;
for (int j = 0; j < n; ++j) {
if (!selected[j] && (v == -1 || min_e[j].w < min_e[v].w))
v = j;
}
if (min_e[v].w == INF) {
cout << "No MST!" << endl;
exit(0);
}
selected[v] = true;
total_weight += min_e[v].w;
if (min_e[v].to != -1)
cout << v << " " << min_e[v].to << endl;
for (int to = 0; to < n; ++to) {
if (adj[v][to] < min_e[to].w)
min_e[to] = {adj[v][to], v};
}
}
cout << total_weight << endl;
}
The adjacency matrix adj[][] of size $n \times n$ stores the weights of the edges, and it uses the weight INF if there doesn't exist an edge between two vertices.
The algorithm uses two arrays: the flag selected[], which indicates which vertices we already have selected, and the array min_e[] which stores the edge with minimal weight to a selected vertex for each not-yet-selected vertex (it stores the weight and the end vertex).
The algorithm does $n$ steps, in each iteration the vertex with the smallest edge weight is selected, and the min_e[] of all other vertices gets updated.
Sparse graphs: $O(m \log n)$¶
In the above described algorithm it is possible to interpret the operations of finding the minimum and modifying some values as set operations.
These two classical operations are supported by many data structure, for example by set in C++ (which are implemented via red-black trees).
The main algorithm remains the same, but now we can find the minimum edge in $O(\log n)$ time. On the other hand recomputing the pointers will now take $O(n \log n)$ time, which is worse than in the previous algorithm.
But when we consider that we only need to update $O(m)$ times in total, and perform $O(n)$ searches for the minimal edge, then the total complexity will be $O(m \log n)$. For sparse graphs this is better than the above algorithm, but for dense graphs this will be slower.
const int INF = 1000000000;
struct Edge {
int w = INF, to = -1;
bool operator<(Edge const& other) const {
return make_pair(w, to) < make_pair(other.w, other.to);
}
};
int n;
vector<vector<Edge>> adj;
void prim() {
int total_weight = 0;
vector<Edge> min_e(n);
min_e[0].w = 0;
set<Edge> q;
q.insert({0, 0});
vector<bool> selected(n, false);
for (int i = 0; i < n; ++i) {
if (q.empty()) {
cout << "No MST!" << endl;
exit(0);
}
int v = q.begin()->to;
selected[v] = true;
total_weight += q.begin()->w;
q.erase(q.begin());
if (min_e[v].to != -1)
cout << v << " " << min_e[v].to << endl;
for (Edge e : adj[v]) {
if (!selected[e.to] && e.w < min_e[e.to].w) {
q.erase({min_e[e.to].w, e.to});
min_e[e.to] = {e.w, v};
q.insert({e.w, e.to});
}
}
}
cout << total_weight << endl;
}
Here the graph is represented via a adjacency list adj[], where adj[v] contains all edges (in form of weight and target pairs) for the vertex v.
min_e[v] will store the weight of the smallest edge from vertex v to an already selected vertex (again in the form of a weight and target pair).
In addition the queue q is filled with all not yet selected vertices in the order of increasing weights min_e.
The algorithm does n steps, on each of which it selects the vertex v with the smallest weight min_e (by extracting it from the beginning of the queue), and then looks through all the edges from this vertex and updates the values in min_e (during an update we also need to also remove the old edge from the queue q and put in the new edge).