Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to use the Kruskal algorithm", the content of the article is simple and clear, easy to learn and understand, now please follow the editor's ideas slowly in depth, together to study and learn "how to use the Kruskal algorithm" bar!

Let's start with the question, what is a parallel search set, and what's the use of it?

In fact, parallel search set, as its name implies, is an algorithm about data structure with two operations: "merge set" and "find set".

1 what is the parallel collection, and the goals to be accomplished.

For example, the link train has to build a part of the road, but each place is scattered into a whole railway network, so many places in China, I can not directly contact every place, so the cost is too high. So we think of it this way, as long as we can go to any place in China from one place, there is no need for every place to have a special railway for each other. This gives rise to a question, how do I know where I am going is in my railway network? Should I build the railway here? It's hard to judge, isn't it? it uses and collects ideas.

And the search set is mainly used to judge whether two vertices in a graph can be connected.

(2) the idea of realizing and searching collection.

Since vertices and vertices can be directly identical, they must be in the same connected network. Therefore, we can regard different connected networks as sets. We need to judge whether the two points are connected, and we can retrieve whether the two points are in the same connected network, and then they can be connected, and vice versa.

Therefore, how should we design so that we can judge whether the two points are in the same net is the crux of the problem.

At this point, we naturally thought that if every point could be represented by a fixed point in the network (let's call it BOSS), then the problem would be solved. For example, in the following picture, we need to judge whether An and B can be connected, and A can look for it.

The BOSS that finds An is also BOSS1,B, and the BOSS that finds B is also BOSS1. It shows that they are in the same connection chart, that is, they can get there.

But this is still troublesome to find BOSS, not easy to find, if it is two trees, then much better, directly take the root node as the BOSS of all nodes, each tree only needs to know who its own superior is, one layer to find up, and finally find the BOSS. For example, to find out whether G and B are on the same net, G starts looking for BOSS,G whose superior is DMague D, whose superior is A Magi An is BOSS, and the BOSS that returns G is A. By the same token, B finds BOSS is also A. It means they're in the same net. For example, if I want to judge whether E and N can be connected, I will find the BOSS of E and the BOSS of N. obviously An is not equal to H. So they can't connect.

To sum up, a lookup set is to merge each heap of elements into a set with the same BOSS. If the BOSS of the two heap elements is different, they are not connected, and vice versa.

3 example code implementation

I think the main body is divided into four parts.

(1) create and look up a set (using an array or a linked list). I'll take an array as an example.

Int parent [maxSize]

I denotes the vertex number parent [I] represents the superior corresponding to I!

Here the subscript represents the vertex number and the element represents its superior (that is, through the superior to find the superior. Can finally find its BOSS).

(2) initialize and check the set

For (int I = 0; I < Nittress I) {parent [I] = I;}

N here represents the number of vertices, first of all, by default, each vertex can not be related to each other, each vertex itself is a set, so a [I] = I; its superior is itself, it is BOSS.

(3) construct an algorithm for finding BOSS, which I give iteratively (recursion can also be written)

Int getBoss (int a) {while (a! = parent [a]) {a = parent [a];} return a;}

If the a passed in the while loop is already BOSS, output it directly, otherwise search for it ([Note] its superior can be found according to the stored value, and its superior continues to search for its superior until it is found by the explanation of await = parent [a].

(4) judging that vertices are merged into the same set (with the same BOSS), I use the iterative method as an example.

Void merge () {int a, b; a = getBoss (c); b = getBoss (d); if (a! = b) {parent [a] = b;}}

C BOSS d represents the subscript of the vertex element passed in. If the two vertices are not equal, it means that they are not in the same tree, that is, there will be no cycle. Put b into the set of a, and from then on they are in the same tree and share a BOSS.

Finally, some examples of practical application are given.

The connectivity of the whole picture. For example, randomly give you two points to determine whether they are connected, or ask you how many connected branches there are in the whole picture, that is, they are divided into independent blocks. Asking how many roads still need to be built is essentially asking for how many connected branches there are. Wait a minute.

Typedef struct// sets up a set of edges {int begin;// the beginning of an edge int end;// the end of an edge the weight of this edge} Edge; int Find (int* parent, int f) / / find the function {while (parent [f]! = f) with the node / if the superior passed by f is not parent [f] / / find its superior according to f. Its superiors continue to look for its superiors If you know parent [f] = f, output {f = parent [f];} return f;} void Kruskal (MGraph G) {Edge edges [numE]; / / define an array of edge sets to store all edge sets [numV] / / define an array to determine whether to form a ring with the edge / / this row converts the adjacency matrix into an edge set array edges and sorts for from smallest to largest.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.