Thuc hanh da xong, gio den ly thuyet ^^

[asmking]

_ Lần trước có ai đó gởi lên diễn đàn các bài tập thực hành môn Giải thuật, mình down về cũng lâu rồi nhưng lâu nay không có dịp xem, mấy bữa nay gần thi nên lấy ra xem thì mới phát hiện bài về giải thuật Kruskal viết sai, chạy không ra kết quả gì hết, mình mất cả đêm mới viết lại được, cũng chưa chắc có đúng không nữa nhưng đã thử qua 2 bộ thử khá phức tạp & đều cho kết quả đúng.

_ Giờ đưa lại nó lên cho các bạn chạy thử xem có còn gì sai sót không nhé

Download bài Giải thuật Kruskal

Phần khai báo

Code:

#define MAX 100

struct oneEdge
{
   int v1;
   int v2;
   int w;
};
struct edgesList
{
   oneEdge edges[MAX];
   int numEdge;
};
struct graph
{
   int numv;
   int matrix[MAX][MAX];
};

_ Khai báo cấu trúc oneEdge dành cho một cạnh đơn.
_ Khai báo cấu trúc graph dành cho đồ thị.
_ Khai báo cấu trúc edgesList dành cho tập các cạnh.

---

Hàm Kruskal()

Code:

edgesList kruskal(edgesList edgesGraph)
{
   edgesList edgesMST; // Cac canh cua Cay bao trum nho nhat(MST)
   oneEdge e;
   int i,v1,v2,n;
   n = 0;
   sortEdgesWeight(edgesGraph); // Sap xep cac canh tang dan theo trong so
   for (i=0;i<edgesGraph.numEdge;i++)
   {
      e = edgesGraph.edges[i];
      if (!testCycle(edgesMST,e.v1,e.v2)) // Neu e la canh ko tao chu trinh
      {
         edgesMST.edges[n] = e;     // thi dua e vao MST
         edgesMST.numEdge=++n;
      }
   }
   return edgesMST;
}

_ Điểm chủ yếu của hàm Kruskal này là 2 hàm sortEdgesWeight() & testCycle().
_ Hàm sortEdgesWeight() có tác dụng sắp xếp các cạnh tăng dần theo trọng số (mình sử dụng giải thuật Selection Sort cho hàm này, các bạn có thể cải tiến bằng Heapsort hay Quicksort gì đó cũng được ).
_ Hàm testCycle() có tác dụng kiểm tra xem cạnh đưa vào có khả năng tạo thành chu trình (cycle) hay không, đây là một hàm đệ qui & nó ngốn khá nhiều thời gian code của mình.

---

Hàm testCycle()

Code:

int testCycle(edgesList eMST, int vFirst, int vEnd)
{
   int i,j,v1,v2,t;
   t=0;
   for (i=0;i<eMST.numEdge;i++)
   {
      if (t) return 1;
      v1 = eMST.edges[i].v1;
      v2 = eMST.edges[i].v2;
      if (vFirst==v1 || vFirst==v2){
         eMST.edges[i].v1 = 0;
         eMST.edges[i].v2 = 0;
         if (v2==vEnd || v1==vEnd)
            return 1;
         if (vFirst==v1)
            t = testCycle(eMST,v2,vEnd);
         else   t = testCycle(eMST,v1,vEnd);
      }
   }
   if (t) return 1;
   return 0;
}

_ Hàm trả về 1 nếu cạnh đưa vào tạo thành chu trình, trả về 0 nếu ngược lại.
_ Trước đây mình chưa viết phần kiểm tra chu trình bao giờ nên hàm này có phần hơi thô sơ, các bạn nào có cách code ngắn hơn & súc tích hơn thì hãy post lên cho mọi người tham khảo nhé.

---

_ Còn giải thuật Prim nữa, nhưng theo mình thấy thì Kruskal khó viết hơn Prim, mình sẽ tham khảo code đã down về sớm hơn, nếu hoàn thành sẽ nhanh chóng post lên cho các bạn, hẹn gặp lại & chúc các bạn ôn bài thật kỹ cho buổi thi thực hành ngày mai nhé

[nguyenthiphuongchi]

cám ơn bạn!Để mình chạy thử xem sao?Có buồn ngủ không bạn?

[asmking]

cám ơn bạn!Để mình chạy thử xem sao?Có buồn ngủ không bạn?

_ Làm không được nên hết buồn ngủ luôn rồi
_ Giờ đi ăn sáng cái rồi chắc về ngủ tới trưa
_ À mình mới kiểm tra bài giải thuật Prim rồi, chạy tốt với 2 bộ thử của mình, có điều bài này viết không theo quy cách lập trình nên mình đọc mệt mắt quá, chắc phải làm lại theo cách của mình thôi
_ Có điều cho thấy rõ là bài Prim này không dùng đệ qui để kiểm tra chu trình như cách mình làm trong giải thuật Kruskal, ở đây nó sử dụng danh sách liên kết để hình thành dần cây MST, mình nghĩ đây cũng là một cách hay & cũng là cái khác của Prim so với Kruskal.

[nguyenthiphuongchi]

Bài của bạn chạy tốt rồi đúng k? Sao bạn không đưa hàm sortEdgesWeight vào luôn. Mình thử chạy bài của bạn làm mà nó báo lỗi là thiếu hàm đó.

[asmking]

Bài của bạn chạy tốt rồi đúng k? Sao bạn không đưa hàm sortEdgesWeight vào luôn. Mình thử chạy bài của bạn làm mà nó báo lỗi là thiếu hàm đó.

_ Bạn có download cái file Kruskal.cpp của mình về không đấy? Cái file đó là bài đầy đủ & chạy được, còn mấy cái code mình post lên là để giải thích thôi
_ Mình đang làm lại bài Prim, hy vọng làm xong trước khi cơn buồn ngủ đến

[nguyenthiphuongchi]

Mình có down rồi.
Chúc bạn thi tốt nha.

[mylinh]

thi thuc hanh lan nay chu yeu la cac bai tap ve do thi thoi ma, hinh nhu minh nghe thay noi vay do

[NguyenTheNam]

cam on ban nhe!

[phuong.ntt-08h1010074]

Thực hành ko thi thậut toán Bruskal,các bạn chừa nó ra.

[asmking]

Thực hành ko thi thậut toán Bruskal,các bạn chừa nó ra.

_ Bạn có thể cho mình hỏi thông tin này bạn nghe ở đâu vậy? Thầy nói chăng?
_ Nếu Kruskal & Prim ko ra thì cũng tốt vì 2 giải thuật này tương đối dài, làm rất mất thời gian
_ Mình cho rằng thi thực hành ngày mai đề sẽ cho nhiều phần nhỏ của các giải thuật chúng ta đã học hoặc tìm cách sử dụng các phần đó để giải quyết một bài toán cụ thể nào đó. Các phần như :
+ Xác định tính liên thông & tính thành phần liên thông của đồ thị (vô hướng hoặc có hướng).
+ Tìm đỉnh có bậc lớn nhất (hoặc nhỏ nhất) trong đồ thị vô hướng.
+ Tính bán bậc vào (ra) của một đỉnh bất kỳ trong đồ thị có hướng.
+ Sắp xếp các đỉnh trong đồ thị theo thứ tự bậc tăng dần (hoặc giảm dần).
+ Phân chia các đỉnh trong đồ thị theo bậc chẳn & lẻ.
+ Tính độ dài đường đi ngắn nhất giữa 2 đỉnh bất kỳ trong đồ thị không có trọng số (hoặc có trọng số, cái này là phải sử dụng BFS)
+ Sắp xếp các cạnh theo theo thứ tự tăng dần (giảm dần) của trọng số.
+ Xác định một cây bao trùm của đồ thị.
+ Tìm cây bao trùm lớn nhất MST của đồ thị vô hướng có trọng số (có thể chọn giữa Kruskal & Prim).

_ Chúng ta sẽ cùng nhau giải quyết những vấn đề nho nhỏ này nhé, tuy hơi muộn nhưng có còn hơn không nhỉ

Hàm verticesDegree() dùng để trả về bậc của 1 đỉnh bất kỳ trong đồ thị
Cách 1

Code:


int verticesDegree(graph g, int v) // hàm nhận vào đồ thị g & đỉnh v cần tìm bậc
{
   int b;
   b=0;
   for(int j=1;j<=g.numv;j++)
         b+=g.a[v][j];
        }
        return b;
}


Cách 2

Code:


int verticesDegree(graph g, int v) // hàm nhận vào đồ thị g & đỉnh v cần tìm bậc
{
   int b;
   b=0;
   for(int i=1;i<=g.numv;i++)
         b+=g.matrix[i][v];
        }
        return b;
}


_ Theo cách này rõ ràng chúng ta quy định nếu đỉnh i & j không nối với nhau thì g.matrix[i][j] = 0
_ Để tìm bậc của 1 đỉnh v bất kỳ ta chỉ cần cộng tất cả trọng số trên hàng v(cách 1) hoặc cột v(cách 2) trong ma trận của đồ thị g.

_ Theo lý thuyết trên chúng ta có thể cho hàm verticesDegree() trả về cả 1 mảng chứa bậc của tất cả các đỉnh trong đồ thị g như sau :

Code:

// Hàm verticesDegree() nhận vào đồ thị g
// & trả về mảng chứa bậc của các cạnh trong đồ thị
int *verticesDegree(graph g)
{
   int a[MAX];
   for(int i=1;i<=g.numv;i++)
   {
      a[i]=0;
      for(int j=1;j<=g.numv;j++)
         a[i] += g.matrix[i][j];
   }
   return a;
}


_ Ở đây mình khai báo kiểu trả về của hàm verticesDegree() là int * tức là con trỏ đến một biến kiểu int. Ta đều biết tên của 1 mảng chính là con trỏ hằng đến phần tử đầu tiên của mảng đó.

[asmking]

_ Tiếp theo là "Tính bán bậc vào(ra) của một đỉnh bất kỳ trong đồ thị có hướng".
_ Ở đây ta xét trường hợp đồ thị có hướng không có trọng số :
+ Bán bậc vào (in-degree) của đỉnh v chính là tổng của tất cả các hàng thuộc cột v.
+ Bán bậc ra (out-degree) của đỉnh v chính là tổng của tất cả các cột thuộc hàng v.
_ Ta có thể code như sau :

Code:

int inDegreeVertices(graph g, int v)
{
   int ideg=0;
   for (int j=0;j<g.numv;j++)
      ideg += g.matrix[j][v];
   return ideg;
}
int outDegreeVertices(graph g, int v)
{
   int odeg=0;
   for (int i=0;i<g.numv;i++)
      odeg += g.matrix[v][j];
   return odeg;
}

_ Lưu ý rằng đây chỉ xét cho đồ thị có hướng không trọng số : g.matrix[i][j] chỉ có thể có 2 giá trị là 0(đỉnh i & j không có cạnh nối) & 1(đỉnh i & j có cạnh nối).

---

_ Tiếp theo là trường hợp đồ thị có hướng, có trọng số :

Code:

int inDegreeVertices(graph g, int v)
{
   int ideg=0;
   for (int j=0;j<g.numv;j++)
      if (g.matrix[j][v] != 0)
         ideg++;
   return ideg;
}
int outDegreeVertices(graph g, int v)
{
   int odeg=0;
   for (int i=0;i<g.numv;i++)
      if (g.matrix[j][v] != 0)
      ideg += g.matrix[j][v];
   return ideg;
}

_ Rất đơn giản phải không nào các bạn, thay vì tính tổng tất cả ta chỉ cần xét xem giữa 2 đỉnh có cạnh nối với nhau hay không (g.matrix[][]!=0), nếu có thì ta cứ tăng biến đếm lên

_ Hy vọng ngày mai sẽ ra những phần tương đối đơn giản như vậy để chúng ta kiếm điểm dễ dàng hơn

[asmking]

_ Nếu ta sắp xếp được các đỉnh theo bậc tăng (giảm) dần thì từ đó có thể dễ dàng tìm ra đỉnh có bậc nhỏ nhất (lớn nhất).
_ Lúc trước trong phần Bậc của một đỉnh bất kỳ & bậc của tất cả các đỉnh trong đồ thị vô hướng ta dùng hàm verticesDegree() để trả về một mảng chứa bậc của tất cả các đỉnh. Bây giờ ta đã có mảng chứa bậc của tất cả các đỉnh, tiếp theo ta chỉ việc viết một hàm dùng để sắp xếp các đỉnh đó theo bậc tăng (giảm) dần.

_ Ta tạo một hàm sortDegreeIncrease() như sau :

Code:

void sortDegreeIncrease(int d[], int n)
{
   int temp;
   for (int i=1;i<=n-1;i++)
      for (j=i+1;j<=n;j++)
         if (d[i]>d[j])
         {
            temp = d[i];
            d[i] = d[j];
            d[j] = temp;   
         }      
}

_ Hàm này nhận vào tham số là một mảng chứa bậc của các đỉnh trong đồ thị & nó sẽ sắp xếp mảng đó tăng dần (increase).
_ Để sửa thành sắp xếp giảm dần, ta chỉ cần sửa đoạn code

Code:

d[i]>d[j]

thành

Code:

d[i]<d[j]

& đổi tên hàm thành sortDegreeDecrease() là xong
_ Ở đây mình dùng giải thuật Selection Sort để sắp xếp, các bạn cũng có thể sử dụng những giải thuật nào khác mà mình biết như Insertion, Buble, Heap hay Quick đều được.
_ Sau khi dùng hàm để sắp xếp lại Mảng chứa bậc của các đỉnh trong đồ thị thì việc tìm đỉnh có bậc nhỏ nhất (lớn nhất) là chuyện quá đơn giản

[phuong.ntt-08h1010074]

Tui đi thực hành, thầy nói là ko cho Kruskal, có thể cho Prim

[mylinh]

ban asmking chuan bi bai tot qua, cam on da post bai len nhe

[luan_hdh]

Còn mấy bài này nửa nè bạn ơi

+ Tính độ dài đường đi ngắn nhất giữa 2 đỉnh bất kỳ trong đồ thị không có trọng số (hoặc có trọng số, cái này là phải sử dụng BFS)
+ Xác định một cây bao trùm của đồ thị.
+ Tìm cây bao trùm lớn nhất MST của đồ thị vô hướng có trọng số (có thể chọn giữa Kruskal & Prim).

[khangbui]

cac ban than men!
Thay dan hom nay thi thuc hanh k co bai Kruskal dau. kruskal chi thi li thuyet thoi cac ban a.

[khangbui]

Cac ban a!
Chieu nay thi TH k co thuat giai Kruskal dau. Do la thong tin do chinh thay Hoa xac nhan trong buoi thuc hanh cuoi cung day. Cac ban xem lai nha.
Chuc cac ban thi tot

[asmking]

_ Không quan trọng đồ thị có trọng số hay không.

_ Ta có 2 hàm spanningTree() & testCycle() như sau :

Code:

graph spanningTree(graph g)
{      
   for (int i=1;i<=g.numv;i++)
      for (j=1;j<=g.numv;j++)         
         if (g.matrix[i][j]>0 && !testCycle(g,j,i))
            g.matrix[i][j] = -1;   
   return g;   
}
int testCycle(graph g,int v1,int v2)
{   
   int j=1;
   while (j<=g.numv && v1!=v2)
      if (g.matrix[v1][j] < 0)
      {
         g.matrix[v][j] = 0;
         v1 = testCycle(g,j,v2);   
         j++;      
      }
   if (v1 == v2) return v2;
   else return 0;
}

_ Hàm testCycle() nhận vào ma trận đồ thị g & 2 đỉnh v1,v2. Nếu cạnh giữa v1 & v2 nằm trong chu trình thì hàm testCycle() trả về một giá trị lớn hơn 0(true), ngược lại hàm trả về 0.
_ Hàm spanningTree() nhận vào một ma trận đồ thị g & trả về một ma trận của cây bao trùm bất kỳ trong đồ thị g với g.matrix[i][j]=-1 (giữa đỉnh i & j có cạnh nối).

_ Buồn ngủ quá, phải đi ngủ để lấy sức chiều nay thi đây, ai xem được gì thì xem đi nhé, chúc mọi người chiều nay thi tốt

[Sponsored content]