Data structure learning (C ++) - Figure [3] (no map) (below)

Minimum span

It is really difficult to say that people are the most difficult to wait. The above has just added several extra edges to "improve reliability", which will come to see how to connect all the vertices with the smallest cost. It may be this spirit of people to make human beings to make progress - look at the 3GHZ CPU is really red, I am still suffering from 500MHz, then think about 8086 ...

As the basic element of the figure is the vertex and the side, from these two directions, two algorithms (starting from side), PRIM algorithm (starting from the vertex). It is said that there is still another way, IMHRI, the reference is limited, and it is not detailed.

Minimally generated tree storage

It is clear that there is no need to store the storage method of common trees, although the name "tree", in fact, who is "the ancestors", "children" is not important. Therefore, it is possible to store as the following MSTEDGE structure array.

Template

Class Mstedge

{

PUBLIC:

MSTEDGE () {}

MSTEDGE (INT V1, INT V2, DIST COST): V1 (V1), V2 (V2), Cost (COST) {}

INT V1, V2;

Dist cost;

Bool Operator> (Const Mstedge & V2) {Return (COST> V2.COST);

Bool Operator <(const mstedge & v2) {return (cost

Bool operator == (const mstedge & v2) {return (COST == V2.cost);

}

Kruskal algorithm

The smallest production tree is talking about whether the N-1 does not produce the shortest circuit. The Kruskal algorithm is the most direct expression of this idea - picking a shortest edge in the remaining edges, see if it is generated, give up, not the selected and then repeat this step. It is very simple to say that it is not so easy - it is not so easy - it is necessary to generate a loop needs and find a minimum heap on the remaining edge (do not need to be sorted on all sorts, so he is the best select).

The complexity of the Kruskal algorithm is O (ELOGE). When e is close to N ^ 2, it is better to see the PRIM algorithm of O (N ^ 2), so he is suitable for sparse. As a sparse map, it is usually stored in the abutment table. In addition, the Kruskal algorithm is less inexpensive than the PRIM algorithm (the initial scanning N ^ 2 "side") is stored. Therefore, it is best to put the Kruskal algorithm in the LINK class.

Template int link :: minSpantree (minstedge * a)

{

MinHeap > e; int I, j, k, l = 0;

Mfsets v (vnum); List :: Iterator iTer;

For (i = 0; i

For (iter = vertices [i] .e-> begin (); it! = vertices [i] .E-> end (); iter )

E.Nsert (Mstedge (I, ITER-> VID, ITER-> COST)); // Establishing the heap for FOR (i = 0; I

{

J = v.find (e.top (). v1); k = v.find (e.top (). v2);

IF (j! = k) {v.merge (j, k); a [l] = e.top (); l ;}

E.POP ();

}

Return L;

}

The following is the implementation of piles and collections

#ifndef heap_h

#define heap_h

#include

Using namespace std;

#define minchild (i) (HEAP [i * 2 1]

Template

Class Minheap

{

PUBLIC:

Void INSERT (const t & x) {hEAP.PUSH_BACK (X); Filterup (Heap.Size () - 1);}

Const T & TOP () {Return HEAP [0];

Void Pop () {heap [0] = Heap.Back (); Heap.Pop_back (); filterdown (0);

Private:

Void Filterup (INT I)

{

For (int J = (i - 1) / 2; j> = 0 && HEAP [J]> HEAP [i]; i = j, j = (i - 1) / 2)

SWAP (HEAP [I], Heap [J]);

}

Void FilterDown (INT i)

{

For (int J = minchild (i); j

SWAP (HEAP [I], Heap [J]);

}

Vector HEAP;

}

#ENDIF

#ifndef mfsets_h

#define mfsets_h

Class Mfsets

{

PUBLIC:

Mfsets: size (maxsize)

{

Parent = new int [size 1];

For (int i = 0; i <= size; i ) parent [i] = -1;

}

~ Mfsets () {delete [] parent;

Void Merge (int root1, int root2) // root1! = root2

{

Parent [root2] = root1;

}

INT Find (int N)

{

IF (PARENT [N] <0) Return N;

Return Find (parent [n]);

}

Private:

Int size;

INT * PARENT;

}

#ENDIF

PRIM algorithm

Another way can be obtained if starting from the vertices. Start with a set of vertices, find the vertices outside the collection to the top of the vertices in this collection, then add this vertex to the collection, modify the vertices of this vertex to the top of the collection to the vertices in the collection The shortest distance generates a change in the change. Because of the need to scan each vertex, the image stored in the abutment matrix is ​​the most suitable PRIM algorithm.

Template int adjmatrix :: minSpantree (mstedge * a) {

Dist * lowc = new dist (VNUM]; int * Nearv = new int [vnum];

INT I, J, K;

For (i = 0; i

For (k = 0; k

{

For (i = 1, j = 0; i

IF (Nearv [I]! = -1 && lowc [i]

a [k] = mstedge (Nearv [J], J, LowC [J]); Nearv [J] = -1; // Insert MST

IF (a [k] .cost == noedge) Return K - 1; // no Edge rebel

For (i = 1; i

IF (Nearv [i]! = -1 && Edge [i] [j]

}

Return K;

}

[Note] What should be 0 or no desi? Obviously 0 reasonably, but it is not easy to use. And, from the perspective of the right map without the right map, NOEDGE is better. Therefore, in my adjacent matrix, the elements on the main diagonal are NOEDGE, not 0 on the book.

test program

Storage and operation separation, I didn't expect an interesting result - for the last non-shaped figure, the algorithm of the minimally generated tree did not know that the algorithm was used.

Template

Bool graph :: minspantree ()

{

Mstedge * a = new mstedge [vnum () - 1];

INT N = DATA.MINSPANTREE (A); Dist Sum = dist ();

IF (n

For (int i = 0; i

{

Cout << '(' << GetV (a [i] .v1) << ',' << getV (a [i] .v2) << ')' << a [i] .cost << ' ;

SUM = a [i] .cost;

}

COUT << Endl << "mincost: << Sum << Endl;

delete [] a;

Return True;

}

The final test diagram data is taken from the Yink version (C ) - I don't know what this group of data is good, Yin version actually has an original painted "Data Structure Algorithm and Application - C Language Description" (Chinese translation) # INCLUDE

Using namespace std;

#include "graph.h"

int main ()

{

Graph > a (100); / / change to LINK Save as Kruskal Algorithm

A.Nsertv ('a'); a.insertv ('b');

A.Nsertv ('c'); a.insertv ('d');

A.NsertV ('e'); a.insertv ('f');

A.Nsertv ('g');

A.NSerte ('A', 'B', 28); A. INSERTE ('A', 'F', 10);

A.NSerte ('b', 'c', 16); A. INSERTE ('c', 'd', 12);

A.NSERTE ('D', 'E', 22); A. INSERTE ('B', 'G', 14);

A.NSerte ('E', 'F', 25); A.NSERTE ('D', 'G', 18);

A.Nserte ('E', 'G', 24);

A.minspantree ();

Return 0;

}