The method of judging whether there is a tree graph is very simple, and it only needs to traverse the graph once with V as the root, so the following algorithm no longer considers the case that the tree graph does not exist.
Before all operations begin, we need to clear all the self-loops in the diagram. Obviously, a self-ring cannot be on any tree graph. Only through this operation can the total complexity of the algorithm be truly guaranteed to be O(VE).
First, choose an edge for every point except the root, and this edge must be the smallest of all edges. Now all the smallest edges are selected. If there is no directed cycle in this edge set, we can prove that this set is the smallest tree graph of this graph. This proof is not difficult. If there is a directed cycle, we call it an artificial vertex and change the weight of the edges in the graph. Suppose a certain point u is here. Let the edge weight pointing to U in this ring be in [u], then for each edge (U, I, W) starting from U, connect the edges of (new, I, W) in the new graph, where New is the newly added artificial vertex; For each edge (i, u, w) that enters u, the edge of the edge (i, new, w-in[u]) is established in the new graph. Why subtract the weight of the edge from in[u]? This will be explained later, and the steps of the algorithm are given here first. Then it can be proved that the weight of the minimum tree graph in the new graph plus the weight sum of the contraction ring in the old graph is the original graph.
The above conclusion will not be proved. Now, according to the above conclusion, explain why the weight of the edge is unchanged and the weight of the edge is subtracted from in [u]. For the smallest tree graph T in the new graph, let the edge pointing to the artificial node be E, and after the artificial node is expanded, the E points to a ring. Assuming that the original E points to U, we will delete the edge in [u] that points to U on the ring, so that we can get the original image. If the weight w'(e) of E in the new graph is the weight w(e) in the original graph minus the weight in [u], then when we delete in[u] and restore E to the original graph, the weight of this tree graph is still the weight of the new graph tree graph, which is exactly the weight of the minimum tree graph. So after expanding the nodes, we still get the minimum tree diagram.
If it is realized wisely, we can find the smallest edge O(E), find the ring O(V) and reduce O(E), among which finding the ring O(V) requires a little skill. So the complexity of each contraction is O(E), and then how many times will it shrink at most? Since we removed all the self-rings at the beginning, we can know that each ring contains at least 2 points. After shrinking to 1 min, the total number of points will be reduced by at least 1. When the whole graph is reduced to only 1 points, the minimum tree graph is unnecessary. So we will only shrink V- 1 times at most, so the total complexity is naturally o.