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;

                                                                   }

                                                                }

Suy nghĩ và phân tích bài tập thuật giải buổi 6

Hướng dẫn code Kruskal

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

-          Dùng ma trận kề biểu diễn đồ thị vô hướng có trọng số.

-          Dùng danh sách cạnh biểu diễn đồ thị có trọng số.

-          Dùng 1 mảng (hay còn gọi là cây) biểu diễn tập hợp lưu trữ các đỉnh đi trước. (Disjoint-set forests)

1/ Ma trận kề

Thành phần : mảng 2 chiều và kích thước

Thao tác      : nhập đồ thị, xuất đồ thị, tạo danh sách cạnh từ ma trận kề

2/ Danh sách cạnh

Thành phần:  mảng cạnh và kích thước.

Thao tác     :  thêm 1 cạnh, xuất danh sách.

v  Cạnh

Thành phần:  đỉnh đầu, đỉnh cuối, trọng số.

 Thao tác    :  tạo cạnh, xuất cạnh

3/ Mảng biểu diễn tập hợp

Nếu ta tổ chức đỉnh của đồ thị kiểu số nguyên thì mảng lưu trữ đỉnh sẽ kiểu số nguyên.

Thao tác     :   Tạo 1 tập mới, tìm tập hợp, hợp 2 tập

• Ví dụ về thành phần cấu trúc:

struct GRAPH{

          int matrix[SIZE][SIZE];

          int n;

};

struct Edge{

          int vbegin;

          int vend;

          int weight;

};

struct SetOfEdge

{

          Edge edge[SIZE];

          int n;

};

int Parent[SIZE]; //(Disjoint-set forests)

•   Ví dụ cài đặt 1 số thao tác trên mảng biểu diễn tập hợp :

void MakeSet(int v)

{

          Parent[v] = -1 ;

}

int FindSet(int u)

{

          int v = u;

          while(Parent[v] >= 0) v = Parent[v];

          return v;

}

void UnionSet(int u,int v) 

{

          int x=FindSet(u);

          int y=FindSet(v);

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

          {

                   Parent[y]+=Parent[x];

                   Parent[x]=y;

          }

          else

          {

                   Parent[x]+=Parent[y];

                   Parent[y]=x;

          }

}

•   Ví dụ thao tác tạo danh sách cạnh từ ma trận kề vô hướng :

SetOfEdge GetSetOfEdge(const GRAPH &T)

{

          SetOfEdge res;

          Edge tempEdge;

          res.n=0;

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

          {

                   for(int j=i;j<T.n;j++) //vì đồ thị vô hướng nên j=i

                   {

                             if(T.matrix[i][j]!=0)

                             {

tempEdge.vbegin=i;

                                       tempEdge.vend=j;

                                       tempEdge.weight=T.matrix[i][j];

                                      insertEdge(tempEdge, res);

                             }

                   }

          }

          return res;

}

II/ Thuật giải

1 thuật giải sắp xếp dãy không giảm (thứ tự tăng dần). Có thể là bubblesort cho dễ cài đặt, hoặc heapsort để giảm độ phức tạp…

Bắt đầu cài đặt dựa vào mã giả:

Mã giả:                                                              Mã C++:

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

                                                                   {

                                                                           SetOfEdge E, A;

                                                                           int u, v, i;

1  A ← Ø                                                               A.n = 0;

2  for each vertex v thuộc V[G]                              for(v = 0 ; v < G.n ; v++)

3           do MAKE-SET(v)                                             MakeSet(v);

4  sort the edges of E                                             E = GetSetOfEdge(G);

    into nondecreasing order by weight w                 BubbleSort(E);

5  for each edge(u,v) thuộc E,                                for(i = 0 ; i < E.n ; i++)

    taken in nondecreasing order by weight               {

                                                                                   u = E.edge[i].vbegin;

                                                                                   v = E.edge[i].vend;

6        do if FIND-SET(u) khác  FIND-SET(v)                   if(FindSet(u) != FindSet(v))

                                                                                   {

7                then A ← A U {(u,v)}                                         insertEdge(E.edge[i] , A);

8                        UNION(u,v)                                                UnionSet(u, v);

                                                                                   }

                                                                              }

9  return A                                                             return A;

                                                                      }