Algorithms of connexity based on pointers

The following algorithms of connexity make it possible to determine quickly if two tops of a graph not directed are connected by a way or not, by creating a table of pointers which implements in fact a forest of trees.

Each tree created by the algorithm corresponds in fact to a related component of the graph: thus two tops will be connected by a way if and only if they belong to the same tree. That is checked by comparing the roots of the respective trees.

One will note that, if these algorithms are effective to know if two tops are connected, they are on the other hand much heavier than the Algorithme of course in width and the Algorithme of in-depth course if it is only a question of knowing if a graph is related.

Notations

The graph in question will be $\ mathcal {G} = \ left ({\ mathcal {S}}, {\ mathcal {has}} \ right)$ , where $\ mathcal {S}$ is the whole of the tops and $\ mathcal {has}$ the whole of the edges, with $\ left (\ mathcal {has} \ subset {\ mathcal {S} \ times \ mathcal {S}} \ right)$ . the graph is not directed .

So as to simplify the implementation of the problem, $\ mathcal {S} = 0; {n-1} \!]$ where N is the number of tops of the graph. The graph will be presented in the form of list of pairs, each pair corresponding to an edge. The implementations will be written in generic language.

General principle

The three algorithms which we will present to you rest on the creation and the regrouping of trees starting from the graph proposed, then on the test of the connexity by checking that all the tops belong finally to the same tree.

One thus creates a table forest of N elements corresponding to each top. Contents of each I - ième box of the table is the top J towards which point the top I : if it is a root, I point towards itself; if not it points towards another top J different of I (i.e. I is a son of J ). As follows:

forêt=j $\ Rightarrow$ I point towards J

At the beginning, each top is root of the tree which it only forms: forest is initialized with values 0,1,…, n-1.

One seeks the root of the tree to which a top in the following recursive way belongs: 1 root (I, forest) (*trouve the root of a node i*) 2 as long as I! = forest to make 3 I: =forêt gives; (*suit pointers until falling on a racine*) 4 turns over I; ; (*retourne the résultat*)

Two tops will be thus connected if and only if they point (directly or indirectly) towards the same root ( root (I, forest) =racine (J, forest) ).

The algorithms of connexity have two facets:

the union : for each edge given, the algorithm connects the two tops in the forest; in other words it makes so that they belong to the same tree. It is this phase which is specific to the algorithms.
the membership : one determines if two tops are well connected by comparing the root of their respective trees. The speed of this operation depends on the selected algorithm because the depth of the trees of the generated forest grows with the execution time.

Fast algorithm of membership

This algorithm is most elementary of the three. It rests on a simple idea: one creates in fact of the trees where the sheets are directly connected to their root. Thus, for each edge (I, J) one records the respective roots r₁ of I and r₂ of J , then one gives to all the elements which had as a root r₁ a new root: r₂ . Thus one connects between them all the elements related to I and J by making them point towards the same root. The union thus proceeds as follows:

1 union1 (I, J, forest) 2 r 1=racine (I, forest) (*ou directly r1=forêt*) 3 r 2=racine (J, forest) (*ou directly r2=forêt*) 4 if r1! = r2 (*si I and J are not already dependant 5 for K going from 0 to n-1 to make 6 if forêt=r1 then (*si the top is related to i*) 7 forest: =r2 (*le to bind to j*) 8 finpour

One will test the membership for I and J in a very fast way since it is enough that forest '' and forest '' is equal (sheets being directly related to the roots), from where the name of fast algorithm of membership.

On the other hand, the operation of union is very slow since for each new pair the algorithm must traverse the entirety of the tree. One can prove easily that the algorithm will carry out $n \ cdot p$ iterations during the phase union, with N the number of tops and p the number of pairs. The number of pairs being about proportional to the number of tops, one has with final algorithm in $O (n^2)$ , which is not very satisfactory. We now will interest we in his symmetrical: fast union.

Fast algorithm of union

Another solution consists in creating trees of structure more complex than those of the preceding algorithm so as to have a union much faster. The principle is the following: when one wants to bind I to J , one seeks initially their root of the manner indicated in the paragraph general principle, then one makes point the root of I towards the root of J : the tree containing I then becomes a under-tree of that containing J .

1 union2 (I, J, forest) 2 r 1=racine (I, forest) (*r1=racine of i*) 3 r 2=racine (J, forest) (*r2=racine of j*) 4 if r1! = r2 (*si the roots are différentes*) 5 forest: =r2 (*on makes point r1 towards r2*)

As you see it, the union is very simple. However, the membership is slow because of the function root: indeed the algorithm must recursively follow pointers to arrive at the root, and this way can in this algorithm long being. The operation union , also using the function root, is it also affected.

In the worst of the cases, the algorithm receives in the order the pairs (0,1), (1,2), (2,3),…, (N2, n-1). It needs then, to determine the connexity, to carry out I iterations for each top I (the operation root requires indeed here I iterations). The membership is then made in $O \ left (n^2 \ right)$ …

Algorithm of balanced union

This last algorithm, hardly more complicated, uses as its name indicates it a slower union, but the compromise is worth the sorrow of it since it exceeds the two preceding algorithms by far. The defect of the preceding algorithm was the length of the ways inside the graphs: the problem is solved here by comparing the size of two trees, and by always connecting the root of smallest to the root of largest. The size of the trees will be stored in an additional table cuts of size N of which all the elements have at the beginning for value 1 . size '' corresponds to the size of the tree having for root I. The implementation is the following one:

1 union3 (I, J, forest, size) 2 r 1=racine (I, forest) (*r1=racine of i*) 3 r 2=racine (J, forest) (*r2=racine of j*) 4 if r1! = r2 (*si the roots are différentes*) 5 if taille if not 9 forest: =r1 (*on makes point r2 towards r1*) 10 size: =taille+taille (*et one increases the size of the tree of r1* root)

Let us take again “worse case” of the fast union: the algorithm initially makes point 1 towards 0 and size takes value 2. Then for the pair (1,2), he sees that the root of 1 is 0, that taille=2 and taille=1 (smaller), therefore 2 will point towards 0 and so on: there is at the end a commonplace tree of which all the tops point towards 0. The membership is in this case as fast as for the fast algorithm of membership!

For this worst algorithm of the cases is that where the edges presented are such as each tree is of equal size: it is shown whereas complexity is in $O \ left (p \ cdot \ ln {N} \ right)$ with p the number of pairs and N the number of tops.

Complexity is thus quasi linear.

Conclusion

There exist other algorithms of connexity using of the pointers, in particular the algorithm by compression of way. However, they are not as simple as the union balanced without to be faster. Thus, the search for a solution based on pointers of linear complexity was a subject of research before Robert Tarjan does not show the impossibility of such a solution in 1975.

To also see

Random links: