Bonus Kruskal

Bonus Kruskal (tiếp theo của bài hướng dẫn kruskal):

Cấu trúc dữ liệu:

Phần trên tôi tổ chức tập hợp bằng 1 mảng Parent toàn cục. Bây giờ tôi sẽ tổ chức 1 cách khác. Tôi sẽ tổ chức 1 cấu trúc DjSetForest (DisjointSetForests) để biểu diễn tập hợp.

struct DjSetForest

{

          int Parent[SIZE];

          int n;

};

Và các thao tác trên tập hợp như MakeSet , FindSet … sẽ được viết lại. Ngoài ra tôi thêm vào thao tác MakeAllSet để MakeSet tất cả phần tử, và ContainCycle để kiểm tra xem 2 số nào đó có cùng tập hợp hay không và đây cũng chính là kiểm tra thêm cạnh tạo bởi 2 đầu mút là 2 số đó vào có chu trình hay không.

Ví dụ:

void MakeSet(DjSetForest &DjSF, int v)

{

          DjSF.Parent[v] = -1;

}

void MakeAllSet(DjSetForest &DjSF)

{

          for(int i=0 ; i<DjSF.n ; i++)

                   MakeSet(DjSF, i);

}

int FindSet(const DjSetForest &DjSF, int u)

{

          int v = u;

          while(DjSF.Parent[v] > 0)

                   v = DjSF.Parent[v];

          return v;

}

void UnionSet(DjSetForest &DjSF, int u,int v) 

{

          int x = FindSet(DjSF, u);

          int y = FindSet(DjSF, v);

          if (DjSF.Parent[x] > DjSF.Parent[y])

          {

                   DjSF.Parent[y] += DjSF.Parent[x];

                   DjSF.Parent[x] = y; //x la nut cha cua y

          }

          else

          {

                   DjSF.Parent[x] += DjSF.Parent[y];

                   DjSF.Parent[y] = x;

          }

}

bool ContainCycle(const DjSetForest &DjSF, Edge e)

{

          return (FindSet(DjSF,e.vbegin) == FindSet(DjSF,e.vend));

}

Và ta cũng cần 1 hàm để chuyển từ danh sách cạnh sang ma trận kề, tôi sẽ dùng cấp phát động và trả về kiểu con trỏ để tiết kiệm tài nguyên, tránh tạo lại và sao chép cả 1 đối tượng GRAPH , những thao tác trước đây nếu bạn muốn tối ưu thì đều có thể làm theo cách này.

GRAPH* GetGraph(const SetOfEdge &E)

{

          int i,j,k;

          int vmax=-1;

          GRAPH* res=new GRAPH;

          for(k=0;k<E.n;k++)

          {

                   if(E.edge[k].vend>vmax) vmax=E.edge[k].vend;

          }

          res->n=vmax+1;

          emptyGRAPH(*res);

          for(k=0;k<E.n;k++)

          {

                   i=E.edge[k].vbegin;

                   j=E.edge[k].vend;

                   res->matrix[i][j]=res->matrix[j][i]=E.edge[k].weight;

          }

          return res;

}

Chú thích: thao tác emptyGRAPH(…) sẽ gán trị 0 cho tất cả các phần tử của ma trận kề

Thuật giải:

Mã giả:                                                              Mã C++:

KRUSKAL(G,w)                                          SetOfEdge Kruskal(const GRAPH &G)

                                                               {

                                                                   SetOfEdge E,F;

                                                                   Edge e;

                                                                   DjSetForest DjSF;

                                                                   DjSF.n=G.n;

                                                                   MakeAllSet(DjSF);

1.  F ← Ø                                                     F.n=0;

                                                                  

2.  Sort the edges of E                                   E=GetSetOfEdge(G);

     into nondecreasing order by weight w        BubbleSort(E);

3.  while |F| < n-1 and E  khác Ø                   while(F.n < G.n-1 && E.n!=0)

                                                                   {

4.     do e ← x|w(x)=min{w(y), y thuộcE}                e=ExtractMin(E);

5.         E  <-- E – {e}                             

6.        if F U {e} not conain cycle                             if(!ContainCycle(DjSF,e))

                                                                             {

               then F ← F U {e}                                             insertEdge(e,F);

                                                                                     UnionSet(DjSF,e.vbegin,e.vend);

                                                                             }

                                                                    }

7.  if |F| < n-1                                               if(F.n < G.n-1)

8.     then G is not connected                                      return NULL;

                                                                   else

                                                                   {

9.     else return T    ›T = (V, F)                                GRAPH* T=GetGraph(F);

                                                                             return T;

                                                                   }

                                                                }