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;

                                                                      }