Announcement

**11520288** · 16-06-2012, 20:55

nghe nói quyển competitive programming sắp ra edition mới, mấy anh hay dùng quyển này cho em hỏi ở TP.HCM mua ở đâu vậy hay phải photo như trước.

**08520001** · 16-06-2012, 20:59

Hiện tại anh đang có tập 2. Nếu em cần anh sẽ cho mượn photo thoi trang nu. Nhưng nó cũng ko khác quyển 1 nhiều lắm.

Nếu em có tập 1 rồi thì anh nghĩ ko cần photo thêm tập 2 đâu. Chỉ khác nhiều ở các bài tập thôi.

**11520288** · 16-06-2012, 21:12

Originally posted by 08520001 View Post

Hiện tại anh đang có tập 2. Nếu em cần anh sẽ cho mượn photo. Nhưng nó cũng ko khác quyển 1 nhiều lắm. Nếu em có tập 1 rồi thì anh nghĩ ko cần photo thêm tập 2 đâu. Chỉ khác nhiều ở các bài tập thôi.

check box tin nhắn nha anh.

**08520001** · 17-06-2012, 17:30

Bài toán cây khung nhỏ nhất trong đồ thị

Cho đồ thị vô hướng liên thông có trọng số, với một cây khung T của G ta gọi trọng số của cây T là tổng trọng số các cạnh trong T. Bài toán đặt ra là trong số các cây khung của G, chỉ ra cây khung có trọng số nhỏ nhất. Để giải quyết bài toán cây khung nhỏ nhất, chúng ta có hai giải thuật khá phổ biển là Kruskal và Prim. Trước khi đi vào phần trình bày chi tiết của hai giải thuật này thoi trang nam. chúng tôi xin được nhắc lại một số kiến thức cơ bản về cây khung của đồ thị :

• Cây là đồ thị vô hướng, liên thông, không có chu trình đơn. Đồ thị vô hướng không có chu trình đơn gọi là rừng (hợp của nhiều cây). (0)
• Xây dựng cây khung : thông thường cây khung của đồ thị được xây dựng bằng phép duyệt đồ thị theo chiều sâu (DFS). Khi đó, các cạnh ứng với các cung trong của quá trình duyệt theo chiều sâu chính là các cạnh của cây khung.

THUẬT TOÁN KRUSKAL

Thuật toán Kruskal được xây dựng dựa trên nguyên lý Greedy như sau :

• Khởi tạo cây khung T rỗng, đồng thời sắp xếp tất cả các cạnh của đồ thị G tăng dần theo trọng số.
• Lần lượt xét các cạnh của đồ thị G theo thứ tự trọng số, nếu cạnh đang xét tạo với các cạnh của cây khung T một chu trình đơn thì bỏ qua. Ngược lại, thêm cạnh đang xét vào cây khung T.
• Quá trình trên kết thúc khi cây khung T có đủ N – 1 cạnh hay ta đã xét hết các cạnh của đồ thị G mà vẫn không tìm đủ N – 1 cạnh cho T (đồ thị G không liên thông).

Để dễ cài đặt, thuật toán Kruskal có thể được phát biểu lại dưới góc nhìn khác như sau :

• Ban đầu, ta xem mỗi đỉnh của đồ thị là một cây con chỉ có một nút.
• Tại mỗi thời điểm ta chọn hai cây con nối lại với nhau bằng một cạnh sao cho trọng số của cạnh đó nhỏ nhất.
• Như vậy, khi xét đến một cạnh (u, v) (theo thứ tự về trọng số) thì ta cần kiểm tra xem u và v có thuộc cùng một cây con hay không. Nếu u và v thuộc về hai cây con khác nhau thì ta dùng cạnh (u, v) để hợp nhất hai cây con đó.
• Quá trình trên sẽ kết thúc khi ta còn lại một cây duy nhất.

Code mẫu:

Code:

struct edge { int u, v, w; }
bool operator < (const st &t1 , const st &t2) 
{ return ( t1.c < t2.c ); }
vector <edge> A, T; // danh sách cạnh
vector <int> parent;
int N;
int root(int x)
{
    if (x != parent[x]) return root(parent[x]); else return x;	
}
void union(int u, int v)
{
	parent[u] = v;
}
void kruskal()
{
	sort(A.begin(), A.end());
	parent = vector <int> (N);
	for (int x = 0; x < N; x++) parent[x] = x;
	for (int x = 0; x < A.size(); x++)
	{
		int u = root(A[x].u), v = root(A[x].v);
		if (u != v) union(u, v);
		if (u != v) res.push_back(A[x]);
		if (res.size() == N – 1) break;
        }
}

Phân tích mô hình cài đặt trên, ta thấy độ phức tạp của thủ tục hợp nhất hai cây con chứa u, v là O(1) và độ phức tạp của thủ tục xác định gốc cây con chứa u trong trường hợp xấu nhất là O(N) (do độ cao của cây có thể đạt tới O(N)). Vòng lặp chính của giải thuật trong trường hợp xấu nhất sẽ duyệt qua M cạnh của đồ thị, mỗi lần xét một cạnh (u, v) bất kỳ ta lại gọi thủ tục tìm gốc (O(N))cho u và v. Do đó, độ phức tạp của giải thuật trong trường hợp xấu nhất là O(MN) (không tính chi phí sắp xếp các cạnh theo độ lớn trọng số).