The minimum spanning tree. Prim's algorithm
Given a weighted undirected graph with vertices and edges. Required to find a subtree of the graph, which would connect all the vertices, and thus has the lowest possible weight (ie, the sum of the weights of the edges). Subtree - a set of edges connecting
vertices, with every vertex can reach any other exactly one simple way.
This subtree is called the minimum spanning tree or just the minimum spanning tree . It is easy to understand that any frame will necessarily contain an edge.
In a natural setting , this problem is as follows: there are cities, and for each pair of compounds known to cost them dear (or know that they can not connect). Required to connect all of the city so that you can get from any city to another, and with the cost of construction of roads would be minimal.
Prim's algorithm
This algorithm is named after American mathematician Robert Prima (Robert Prim), which opened this algorithm in 1957. However, even in 1930, this algorithm was discovered by Czech mathematician Wojtek Jarnik (Vojtěch Jarník). Furthermore, Edgar Dijkstra (Edsger Dijkstra) in 1959 as invented this algorithm independently.
Description of the algorithm
Himself algorithm has a very simple form. Seeking the minimum spanning tree is built gradually, adding he edges one by one. Originally skeleton relies consisting of a single vertex (it can be chosen arbitrarily). Then the minimum weight is selected edge emanating from this vertex and added to the minimum frame. Thereafter skeleton already contains two peaks and looking for an edge, and adds the minimum weight, having one end in one of two selected peaks, and the other - on the contrary, all other than these two. And so on,
i.e. whenever sought a minimum weight edge, one end of which is - has already taken in the top of the skeleton, and the other end - is not taken, and this edge is added to the frame (if there are multiple edges, you can take any). This process is repeated until the frame will not yet contain all peaks (or, equivalently, a rib).
As a result, the skeleton will be built, is minimal. If the graph was not initially connected, then the skeleton will not be found (the number of selected edges will be less ).
Proof
Suppose that the graph was connected, ie, answer there. We denote by skeleton found Prim's algorithm, and through - the minimum spanning tree. Obviously, that is indeed the backbone (ie, a subtree of the graph ). We show that the weight and the same.
Consider the first time when the rib are added, is not included in the optimum backbone . We denote this edge through the ends of it - through and , and the set included at that time in the skeleton of the vertices - through (according to the algorithm , or vice versa). Advantageously the skeleton vertices and connected in some way ; in this way we find any edge , one end of which lies in , and the other - no. Since the Prim algorithm chose the rib edges instead , it means that the weight of the edge is greater than or equal to the weight of the edge .
Now remove from the edge , and add an edge . By just said the weight of the core as a result could not have increased (decreased he also could not because it was the best). In addition, no longer a skeleton (that connection is not broken, it is easy to make sure we closed the way to the ring, and then remove them from this cycle, one edge).
Thus we have shown that it is possible to select the optimal framework so that it will include an edge . Repeating this procedure as many times, we see that we can choose the best frame so that it matches with . Consequently, the weight of the construction of algorithms Prima minimal, as required.
Sale
Time of the algorithm depends essentially on how we produce search next minimum matching edges among edges. There can be different approaches lead to different asymptotics and different implementations.
Trivial Pursuit: Algorithms for and
If you look for an edge every time just browsing among all possible options, then
asymptotically be required viewing edges to find among all the valid edge with the lowest weight. The total amount to the asymptotic behavior of the algorithm in this
case , in the worst case there - too slow algorithm.
This algorithm can be improved if the view each time, not all the edges, and only one edge of each pre-selected top. For this example, you can sort the edges of each vertex in
ascending order of the weights, and store a pointer to the first valid edge (recall permissible only those edges that lead to the set is not selected vertices). Then, if these pointers to recalculate each time you add an edge to the backbone, the total asymptotic behavior of the algorithm will , but first need to sort all edges for that in the worst case (for dense graphs) gives the asymptotic behavior .
Below we consider two slightly different algorithm: for dense and sparse graphs, eventually getting much better asymptotic behavior.
The case of dense graphs: an algorithm for
Approaching the matter search smallest rib on the other hand: for each is not selected will be stored a minimum edge going into an already selected vertex.
Then, at the current step to make the choice of the minimum edges, you just have to see these minimum ribs at each vertex is not selected yet - be the asymptotic behavior . But now, when added to the next frame edges and vertices of these pointers must be recalculated. Note that these pointers can only decrease, ie each vertex not yet viewed any need to leave it without changing the pointer or give it the weight of the edge in the newly added vertex. Therefore, this phase can also be done for .
Thus, we have an option of Prim's algorithm with asymptotic behavior .
In particular, such an implementation is particularly useful for solving the so-called problem of the Euclidean minimum spanning tree when given points in the plane, the distance between which is measured by the standard Euclidean metric, and you want to find the skeleton of minimum weight that connects them all (and adding new vertices anywhere elsewhere is prohibited). This problem is solved by the algorithm described here for
the time and memory, which does not turn out to achieve Kruskal's algorithm . The implementation of Prim's algorithm for a graph specified by adjacency matrix : // входные данные
int n;
vector < vector<int> > g;
const int INF = 1000000000; // значение "бесконечность"
// алгоритм
vector<bool> used (n);
vector<int> min_e (n, INF), sel_e (n, -1);
min_e[0] = 0;
for (int i=0; i<n; ++i) { int v = -1;
for (int j=0; j<n; ++j)
if (!used[j] && (v == -1 || min_e[j] < min_e[v])) v = j;
if (min_e[v] == INF) { cout << "No MST!";
exit(0);
}
used[v] = true;
if (sel_e[v] != -1)
cout << v << " " << sel_e[v] << endl;
for (int to=0; to<n; ++to)
if (g[v][to] < min_e[to]) { min_e[to] = g[v][to];
sel_e[to] = v;
} }
The input is the number of vertices and the matrix size , which marked the edges of weight, and cost of , if there is no corresponding edge. The algorithm
supports three arrays: flag means that the top is included in the frame, the size of the smallest allowable weight keeps the edges from a vertex , and the element contains the smallest end of the rib (it is necessary to bring the edges of the reply). The algorithm makes steps, each of which selects the top of the lowest
mark , marks it , and then looks at all the edges of this vertex, recounting their labels.
The case of sparse graphs: an algorithm for
In the above-described algorithm, one can see the operation of finding the minimum standard in the set and change values in the set. These two operations are classic, and perform many data structures, for example, implemented in C ++, the red-black tree set.
Within the meaning of the algorithm remains exactly the same, but now we can find the minimum edge over time . On the other hand, the time for recalculation pointers now be even worse than in the above algorithm.
If we consider that there will be calculations of the original indexes and searches the minimum edge, then the asymptotic behavior of the total amount
- for sparse graphs is better than both of the above algorithm, but in dense graphs, this algorithm is slower than the previous one.
The implementation of Prim's algorithm for a graph specified by adjacency lists : // входные данные
int n;
vector < vector < pair<int,int> > > g;
const int INF = 1000000000; // значение "бесконечность"
// алгоритм
vector<int> min_e (n, INF), sel_e (n, -1);
min_e[0] = 0;
set < pair<int,int> > q;
q.insert (make_pair (0, 0));
for (int i=0; i<n; ++i) { if (q.empty()) {
cout << "No MST!";
exit(0);
}
int v = q.begin()->second;
q.erase (q.begin());
if (sel_e[v] != -1)
cout << v << " " << sel_e[v] << endl;
for (size_t j=0; j<g[v].size(); ++j) { int to = g[v][j].first,
cost = g[v][j].second;
if (cost < min_e[to]) {
q.erase (make_pair (min_e[to], to));
min_e[to] = cost;
sel_e[to] = v;
q.insert (make_pair (min_e[to], to));
} } }
The input is the number of vertices and adjacency lists: - a list of all the edges emanating from the vertex , in the form of pairs (second end edge weight of the edge). The algorithm maintains two arrays: the value keeps the weight of the smallest
allowable edges from the vertex and the element contains the smallest end of the rib (it is necessary to bring the edges of the reply). Additionally, a queue of all the nodes in increasing order of their labels . The algorithm makes steps, each of which selects the top of the lowest mark (simply removing it from the queue), and then looks at all the edges of this vertex, recounting their labels (when calculated from the queue, we remove the old value, and then we place a new back) .
The analogy with the Dijkstra algorithm
In the two algorithms described just seen quite a clear analogy with the Dijkstra's algorithm : it has the same structure ( phase, each of which first selects the optimal edge is added to the response, and then recalculated values for all vertices not yet
selected). Moreover, Dijkstra's algorithm also has two options for implementation: for and (of course we here do not consider the possibility of using complex data structures to achieve even smaller asymptotics).
If you look at the Prim algorithm and Dijkstra's more formally, it turns out that they are all identical to each other except for the weighting function peaks: in Dijkstra's algorithm at each vertex supported length of the shortest path (ie the sum of the weights of some edges), the Prim's algorithm to each vertex is attributed only minimum weight edge leading into the set of vertices already taken.
At the implementation level, this means that after the addition of the next vertex in the set of selected vertices, when we begin to see all the edges of the vertex, the algorithm Prima pointer is updated weight of the edge , and Dijkstra's algorithm - mark distance updated sum labels and edge weight . The rest of these two algorithms can be considered identical (though they are very different and solve the problem).
Properties of the minimum spanning tree
• Maximum frame can also be found Prim's algorithm (for example, replacing all the weights of edges on the opposite: the algorithm does not require the non- negativity of the weights of edges).
• The minimum spanning tree is unique , if the weights of all edges are different. Otherwise, there may be some minimum spanning tree (which one will be selected Prim's algorithm depends on the order in view of edges / vertices with the same weights / pointers)
• The minimum spanning tree is also the core, the minimum for the product of all edges (assuming that all weights are positive). In fact, if we replace the weights of all edges to their logarithms, it is easy to notice that in the algorithm will not
change anything, and will be found the same edges.
• The minimum spanning tree is a spanning tree with minimum weight of the heaviest edges . Most clearly this statement is understandable if we consider the work of Kruskal's algorithm .
• The criterion of minimal core: core is minimal if and only if for every edge not belonging to the skeleton, the cycle formed by the addition of this edge to the core, contains no harder edges of the rib. In fact, if for some edge turned out that it is easier for some ribs formed loop, it is possible to obtain a lighter skeleton (adding this edge into the core, and removing the heaviest edge of the loop). If this condition is not met for any of the edges, all the edges do not improve the weight of the core when they are added.
The minimum spanning tree. Kruskal's algorithm
Given a weighted undirected graph. Required to find a subtree of the graph, which would connect all the vertices, and thus has the lowest weight (ie, the sum of the weights of edges) of all. This subtree is called the minimum spanning tree or just the minimum spanning tree.
It will discuss several important facts related to the minimum spanning tree, then be considered Kruskal's algorithm in its simplest implementation.
Properties of the minimum spanning tree
• The minimum spanning tree is unique, if the weights of all edges are different . Otherwise, there may be a minimum number of cores (specific algorithms typically receive one of the possible core).
• The minimum spanning tree is also a skeleton with a minimum product of the weights of edges.
(proved it's easy enough to replace the weights of all edges to their logarithms)
• The minimum spanning tree is also a skeleton with a minimum weight of the heavy edges .
(This follows from the validity of Kruskal's algorithm)
• The skeleton of the maximum weight is sought is similar to the skeleton of minimum weight, enough to change the signs of all the ribs on the opposite and perform any of the minimum spanning tree algorithm.
Kruskal's algorithm
This algorithm has been described by Kruskal (Kruskal) in 1956
Kruskal's algorithm initially assigns each vertex in his tree, and then gradually brings these trees, combining the two at each iteration of some tree some edge. Before the start of the algorithm, all edges are sorted by weight (in decreasing order). Then begins the process of unification: all edges are moving from first to last (in the sort order), and if the current edges of the ends belong to different subtrees, these subtrees are merged, and the edge is added to the answer. At the end iterate over all edges vertices will belong to the same subtree, and the answer is found.
The simplest implementation
This code is directly implements the algorithm described above, and runs in O (M log N + N 2 ) . Sort ribs require O (M log N) operations. Vertices belonging to a particular subtree stored simply by using an array tree_id - there is stored for each vertex tree number to which it belongs. For each edge we have O (1) determine whether it belongs to the ends of
different trees. Finally, the union of the two trees is carried out for the O (N) simply passes through the array tree_id. Given that all the operations of union is N-1, we obtain the asymptotic behavior of O (M log N + N 2 ) .
int m;
vector <pair <int, pair <int, int>>> g (m); // Weight - the top 1 - 2 vertex
int cost = 0;
vector <pair <int, int>> res;
sort (g.begin (), g.end ());
vector <int> tree_id (n);
for (int i = 0; i <n; ++ i) tree_id [i] = i;
for (int i = 0; i <m; ++ i) {
int a = g [i] .second.first, b = g [i] .second.second, l = g [i] .first;
if (tree_id [a]! = tree_id [b]) {
cost + = l;
res.push_back (make_pair (a, b));
int old_id = tree_id [b], new_id = tree_id [a];
for (int j = 0; j <n; ++ j)
if (tree_id [j] == old_id)
tree_id [j] = new_id;
} }
Improved implementation
Using the data structure "system of disjoint sets" can write faster implementation of Kruskal's algorithm with the asymptotic O (M log N) .
The minimum spanning tree. Kruskal's algorithm with a system of disjoint sets
A description of the problem and the algorithm of Kruskal see. here .
There will be reviewed implementation using a data structure "a system of disjoint sets"
(DSU) , which will reach the asymptotic behavior of O (M log N) .
Description
Just as in the simple version of Kruskal's algorithm, we can sort all edges in non-decreasing weight. Then place each vertex in your tree (ie their set) by calling the DSU MakeSet - it will take a total of O (N). Loop through all the edges (in sorted order) and for each edge in O (1) determine whether it belongs to the ends of different trees (with two calls FindSet O
(1)). Finally, the union of two trees will be calling the Union - also in O (1). Total we obtain the asymptotic behavior of O (M log N + N + M) = O (M log N).
Implementation
To reduce the volume of code and carry out all operations are not as separate functions, but directly in the code of Kruskal's algorithm.
Here we will use a randomized version of the DSU.
vector <int> p (n);
int dsu_get (int v) {
return (v == p [v])? v: (p [v] = dsu_get (p [v]));
}
void dsu_unite (int a, int b) { a = dsu_get (a);
b = dsu_get (b);
if (rand () & 1) swap (a, b);
if (a! = b)
p [a] = b;
}
... In the function main (): ...
vector <pair <int, pair <int, int>>> g; // Weight - the top 1 - 2 vertex
... Read Count ...
int cost = 0;
vector <pair <int, int>> res;
sort (g.begin (), g.end ());
p.resize (n);
for (int i = 0; i <n; ++ i) p [i] = i;
for (int i = 0; i <m; ++ i) {
int a = g [i] .second.first, b = g [i] .second.second, l = g [i] .first;
if (dsu_get (a)! = dsu_get (b)) { cost + = l;
res.push_back (g [i] .second);
dsu_unite (a, b);
} }
Kirchhoff matrix theorem. Finding the number of spanning trees
Ask a connected undirected graph of its adjacency matrix. Multiple edges in the graph are allowed. Required to count the number of different spanning trees of the graph.
The below formula belongs Kirchhoff (Kirchhoff), who proved it in 1847
Kirchhoff matrix theorem
Take the adjacency matrix of the graph G, we replace each element of this matrix to the opposite, and instead of the diagonal element of A i, i put the degree of the vertex i (if there are multiple edges, the vertex degree they are considered with its multiplicity). Then,
according to the Kirchhoff matrix theorem, all the cofactors of the matrix are equal, and equal to the number of spanning trees of the graph. For example, you can delete the last row and the last column of the matrix, and the modulus of its determinant is equal to the required number.
Determinant of the matrix can be found for the O (N 3 ) using the Gauss method or the method Kraut .
The proof of this theorem is quite difficult and is not presented here (see., Eg, coming VB
"The problem of dimers and Kirchhoff theorem").
Communication with the laws of Kirchhoff in an electrical circuit