Bài Tập Tìm Cây Khung Nhỏ Nhất Có Lời Giải

Bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree – MST) là một bài toán kinh điển trong lý thuyết đồ thị, với nhiều ứng dụng thực tế trong các lĩnh vực như mạng máy tính, thiết kế mạng lưới giao thông, và phân cụm dữ liệu. Bài viết này sẽ giới thiệu về bài toán tìm cây khung nhỏ nhất, các thuật toán phổ biến để giải quyết bài toán này, cùng với lời giải chi tiết cho một số bài tập ví dụ.

Tìm Hiểu Về Cây Khung Nhỏ Nhất

Trong lý thuyết đồ thị, một đồ thị là một tập hợp các đỉnh và các cạnh nối giữa các đỉnh. Một cây khung của một đồ thị là một đồ thị con không có chu trình và kết nối tất cả các đỉnh của đồ thị ban đầu. Cây khung nhỏ nhất của một đồ thị có trọng số là cây khung có tổng trọng số các cạnh là nhỏ nhất.

Thuật Toán Tìm Cây Khung Nhỏ Nhất

Có nhiều thuật toán để tìm cây khung nhỏ nhất, trong đó hai thuật toán phổ biến nhất là thuật toán Prim và thuật toán Kruskal.

1. Thuật Toán Prim

Thuật toán Prim bắt đầu từ một đỉnh bất kỳ trong đồ thị và mở rộng dần cây khung bằng cách thêm cạnh có trọng số nhỏ nhất nối đỉnh hiện tại với một đỉnh chưa được kết nối. Quá trình này tiếp tục cho đến khi tất cả các đỉnh đều được kết nối.

// Giả sử đồ thị được biểu diễn bằng ma trận kề G
// với G[i][j] là trọng số cạnh nối đỉnh i và đỉnh j

function primMST(G) {
  const numVertices = G.length;
  const mstSet = new Array(numVertices).fill(false);
  const key = new Array(numVertices).fill(Infinity);
  const parent = new Array(numVertices).fill(-1);

  key[0] = 0;

  for (let count = 0; count < numVertices - 1; count++) {
    let minKey = Infinity, u = -1;
    for (let v = 0; v < numVertices; v++) {
      if (!mstSet[v] && key[v] < minKey) {
        minKey = key[v];
        u = v;
      }
    }

    mstSet[u] = true;

    for (let v = 0; v < numVertices; v++) {
      if (G[u][v] !== 0 && !mstSet[v] && G[u][v] < key[v]) {
        parent[v] = u;
        key[v] = G[u][v];
      }
    }
  }

  // In cây khung nhỏ nhất
  for (let i = 1; i < numVertices; i++) {
    console.log(parent[i] + " - " + i);
  }
}

2. Thuật Toán Kruskal

Thuật toán Kruskal sắp xếp các cạnh theo trọng số tăng dần. Sau đó, thuật toán duyệt qua danh sách các cạnh và thêm cạnh vào cây khung nếu cạnh đó không tạo thành chu trình với các cạnh đã được thêm trước đó. Quá trình này tiếp tục cho đến khi tất cả các đỉnh đều được kết nối.

// Giả sử đồ thị được biểu diễn bằng danh sách cạnh edges
// với mỗi cạnh là một mảng [u, v, w]
// trong đó u, v là hai đỉnh của cạnh và w là trọng số

function kruskalMST(edges, numVertices) {
  edges.sort((a, b) => a[2] - b[2]);

  const parent = new Array(numVertices);
  for (let i = 0; i < numVertices; i++) {
    parent[i] = i;
  }

  function find(i) {
    if (parent[i] !== i) {
      parent[i] = find(parent[i]);
    }
    return parent[i];
  }

  function union(x, y) {
    parent[find(x)] = find(y);
  }

  const mst = [];
  let edgeCount = 0;
  let i = 0;

  while (edgeCount < numVertices - 1) {
    const [u, v, w] = edges[i];
    i++;

    const x = find(u);
    const y = find(v);

    if (x !== y) {
      mst.push([u, v, w]);
      edgeCount++;
      union(x, y);
    }
  }

  // In cây khung nhỏ nhất
  for (const [u, v, w] of mst) {
    console.log(u + " - " + v + ": " + w);
  }
}

Ví dụ về thuật toán tìm cây khung nhỏ nhất

Bài Tập Ví dụ

Cho đồ thị vô hướng có trọng số như sau:

    2
  A---B
 /  / 
3  1  4  2
/   C---D
5   / 
  E---F
    3

Yêu cầu: Tìm cây khung nhỏ nhất của đồ thị.

Lời giải:

Sử dụng thuật toán Prim:

Chọn đỉnh A làm đỉnh bắt đầu.
Chọn cạnh AB có trọng số nhỏ nhất (1).
Chọn cạnh BC có trọng số nhỏ nhất (2).
Chọn cạnh CD có trọng số nhỏ nhất (4).
Chọn cạnh EF có trọng số nhỏ nhất (3).

Cây khung nhỏ nhất tìm được là: AB – BC – CD – EF với tổng trọng số là 10.

Sử dụng thuật toán Kruskal:

Sắp xếp các cạnh theo trọng số tăng dần: AB (1), BC (2), EF (3), AC (3), CD (4), AD (5), BE (5).
Chọn cạnh AB (1).
Chọn cạnh BC (2).
Bỏ qua cạnh AC (3) vì nó tạo thành chu trình với AB và BC.
Chọn cạnh EF (3).
Chọn cạnh CD (4).

Cây khung nhỏ nhất tìm được là: AB – BC – EF – CD với tổng trọng số là 10.

Kết Luận

Bài toán tìm cây khung nhỏ nhất là một bài toán quan trọng với nhiều ứng dụng thực tế. Thuật toán Prim và Kruskal là hai thuật toán hiệu quả để giải quyết bài toán này. Hi vọng bài viết này đã giúp bạn hiểu rõ hơn về bài toán tìm cây khung nhỏ nhất và các phương pháp giải quyết.

FAQ

1. Cây khung nhỏ nhất có duy nhất không?

Không nhất thiết. Một đồ thị có thể có nhiều cây khung nhỏ nhất khác nhau nếu có nhiều cạnh có cùng trọng số nhỏ nhất.

2. Độ phức tạp của thuật toán Prim và Kruskal là bao nhiêu?

Độ phức tạp của thuật toán Prim là O(V^2) với V là số đỉnh. Độ phức tạp của thuật toán Kruskal là O(E log E) với E là số cạnh.

3. Ứng dụng của bài toán tìm cây khung nhỏ nhất trong thực tế?

Bài toán tìm cây khung nhỏ nhất được ứng dụng trong nhiều lĩnh vực như thiết kế mạng lưới giao thông, mạng máy tính, phân cụm dữ liệu…

Bạn Cần Hỗ Trợ?

Nếu bạn cần hỗ trợ thêm về Bài Tập Tìm Cây Khung Nhỏ Nhất Có Lời Giải hoặc bất kỳ vấn đề nào khác, hãy liên hệ với chúng tôi:

Số Điện Thoại: 02033846993
Email: [email protected]
Địa chỉ: X2FW+GGM, Cái Lân, Bãi Cháy, Hạ Long, Quảng Ninh, Việt Nam

Chúng tôi có đội ngũ chăm sóc khách hàng 24/7 luôn sẵn sàng hỗ trợ bạn.