Đơn giản hóa quy trình làm việc của bạn: Tìm kiếm miniwebtool.
Thêm
> Máy tính Cây khung nhỏ nhất
 

Máy tính Cây khung nhỏ nhất

Tính Cây khung nhỏ nhất (MST) của một đồ thị có trọng số bằng thuật toán Kruskal hoặc Prim. Tính năng minh họa đồ thị tương tác, theo dõi thuật toán từng bước và hiệu ứng chọn cạnh.

Máy tính Cây khung nhỏ nhất

Thử các đồ thị ví dụ này:

Đơn giản (5 nút) Mạng lưới (7 nút) Thuật toán Prim (6 nút) Lớn (12 nút)
Định dạng: nút1, nút2, trọng số — một cạnh mỗi dòng. MST hoạt động trên đồ thị vô hướng. Tất cả trọng số phải không âm.

Embed Máy tính Cây khung nhỏ nhất Widget

Giới thiệu về Máy tính Cây khung nhỏ nhất

Chào mừng bạn đến với Máy tính Cây khung nhỏ nhất, một công cụ tương tác để tính toán MST của một đồ thị có trọng số bằng thuật toán Kruskal hoặc Prim. Cho dù bạn đang học lý thuyết đồ thị, thiết kế hạ tầng mạng hay tối ưu hóa phân bổ nguồn lực, máy tính này cung cấp một khám phá trực quan, từng bước về hai thuật toán nền tảng trong tối ưu hóa tổ hợp.

Cây khung nhỏ nhất (MST) là gì?

Cây khung nhỏ nhất của một đồ thị vô hướng, có trọng số và liên thông là một tập hợp con các cạnh sao cho:

  • Kết nối tất cả các đỉnh lại với nhau (spanning - khung)
  • Không chứa chu trình (tree - cây)
  • Có tổng trọng số cạnh nhỏ nhất có thể

Đối với một đồ thị có V đỉnh, một MST luôn có đúng V - 1 cạnh. Nếu đồ thị không liên thông, kết quả là một Rừng khung nhỏ nhất — một tập hợp các MST cho mỗi thành phần liên thông.

Tính chất MST
$$|E_{MST}| = |V| - 1 \quad \text{và} \quad W_{MST} = \sum_{e \in E_{MST}} w(e) \text{ được tối thiểu hóa}$$

Thuật toán Kruskal

Thuật toán Kruskal là một thuật toán tham lam dựa trên cạnh, xây dựng MST bằng cách xử lý các cạnh theo thứ tự trọng số tăng dần. Nó sử dụng cấu trúc dữ liệu Union-Find (Hợp nhất-Tìm kiếm) để phát hiện chu trình một cách hiệu quả.

Mã giả Kruskal

function Kruskal(Graph):
  MST ← tập rỗng
  Sắp xếp tất cả các cạnh theo trọng số (tăng dần)
  Khởi tạo Union-Find cho tất cả các đỉnh

  for each cạnh (u, v, w) trong danh sách đã sắp xếp:
    if Find(u) ≠ Find(v):  // thuộc các thành phần khác nhau
      MST ← MST ∪ {(u, v, w)}
      Union(u, v)  // hợp nhất các thành phần

  return MST
Độ phức tạp thời gian của Kruskal
$$O(E \log E) = O(E \log V)$$

Thuật toán Prim

Thuật toán Prim là một thuật toán tham lam dựa trên đỉnh, phát triển MST từ một đỉnh bắt đầu. Tại mỗi bước, nó thêm cạnh rẻ nhất kết nối một đỉnh trong cây với một đỉnh ngoài cây.

Mã giả Prim

function Prim(Graph, start):
  MST ← tập rỗng
  inMST ← {start}
  PQ ← hàng đợi ưu tiên với các cạnh từ start

  while PQ không rỗng and |inMST| < |V|:
    (w, u, v) ← lấy min từ PQ
    if v ∉ inMST:
      MST ← MST ∪ {(u, v, w)}
      inMST ← inMST ∪ {v}
      Thêm tất cả các cạnh từ v vào PQ

  return MST
Độ phức tạp thời gian của Prim (Heap nhị phân)
$$O((V + E) \log V)$$

Kruskal so với Prim: Khi nào nên dùng cái nào?

Tính năngKruskalPrim
Cách tiếp cậnDựa trên cạnh (sắp xếp toàn cục)Dựa trên đỉnh (phát triển cục bộ)
Cấu trúc dữ liệuUnion-FindHàng đợi ưu tiên (Priority Queue)
Độ phức tạp thời gian\( O(E \log E) \)\( O((V + E) \log V) \)
Phù hợp nhất choĐồ thị thưaĐồ thị dày đặc
Đồ thị không liên thôngTạo ra rừng khungChỉ bao phủ thành phần của nút bắt đầu
Khả năng song song hóaDễ dàng song song hóa hơnBản chất là tuần tự

Cách sử dụng máy tính này

  1. Xác định các cạnh của đồ thị: Nhập các cạnh theo định dạng node1, node2, trọng số, mỗi cạnh một dòng. MST hoạt động trên đồ thị vô hướng, vì vậy mỗi cạnh hoạt động theo cả hai hướng.
  2. Chọn thuật toán: Chọn Kruskal cho đồ thị thưa hoặc Prim cho đồ thị dày đặc. Cả hai đều tạo ra MST tối ưu.
  3. Đặt nút bắt đầu (chỉ dành cho Prim): Tùy chọn chỉ định nơi thuật toán Prim bắt đầu. Điều này ảnh hưởng đến thứ tự chọn cạnh nhưng không ảnh hưởng đến tổng trọng số MST.
  4. Tính toán MST: Nhấp vào "Tìm MST" để chạy thuật toán. Khám phá hình ảnh trực quan hóa tương tác, bảng cạnh và theo dõi từng bước.
  5. Xem qua các bước: Sử dụng các nút Tiếp theo/Trước đó để xem thuật toán thực thi từng bước, với phần tô màu trực tiếp trên canvas.

Hiểu kết quả

Bảng cạnh MST

Hiển thị mọi cạnh được chọn cho MST, theo thứ tự chúng được thêm vào, cùng với trọng số riêng lẻ và tổng trọng số MST.

Trực quan hóa đồ thị

Canvas tương tác hiển thị đồ thị của bạn với các thành phần được mã hóa màu:

  • Các nút và cạnh màu xanh lá cây = Một phần của MST
  • Phần tô màu cam = Hiện đang được kiểm tra
  • Các thành phần màu xám = Chưa thuộc MST

Theo dõi từng bước

Hiển thị từng quyết định của thuật toán: cạnh nào đang được xem xét, nó được chấp nhận hay bị từ chối (và tại sao), và trạng thái hiện tại của quá trình xây dựng MST.

Các ứng dụng thực tế của MST

Thiết kế mạng

Ứng dụng kinh điển nhất. Khi kết nối các nút (thành phố, máy chủ, thiết bị điện) với tổng chiều dài cáp, sợi quang hoặc đường ống tối thiểu, MST cung cấp giải pháp tối ưu. Các công ty viễn thông sử dụng các thuật toán dựa trên MST để giảm thiểu chi phí cơ sở hạ tầng.

Phân tích cụm

Trong học máy và khoa học dữ liệu, phân cụm dựa trên MST (như single-linkage clustering) nhóm các điểm dữ liệu bằng cách loại bỏ các cạnh dài nhất khỏi MST. Điều này tạo ra các cụm tự nhiên mà không cần chỉ định trước số nhóm.

Phân đoạn hình ảnh

Các thuật toán thị giác máy tính sử dụng MST để phân đoạn hình ảnh thành các vùng có ý nghĩa. Các pixel là các nút, trọng số cạnh đại diện cho sự khác biệt về màu sắc/cường độ, và việc cắt các cạnh MST giúp tách biệt các đối tượng khác nhau.

Thuật toán xấp xỉ

MST cung cấp một xấp xỉ bậc 2 cho Bài toán người bán hàng (TSP) hệ mét. Trọng số MST là một cận dưới cho hành trình TSP tối ưu, và việc nhân đôi các cạnh MST tạo ra một hành trình trong phạm vi gấp 2 lần tối ưu.

Thiết kế mạch

Thiết kế chip VLSI sử dụng MST (thông qua các biến thể cây Steiner) để giảm thiểu tổng chiều dài dây nối các linh kiện trên bảng mạch, giảm độ trễ tín hiệu và chi phí sản xuất.

Các thuộc tính chính của MST

  • Tính chất cắt (Cut Property): Đối với bất kỳ lát cắt nào của đồ thị, cạnh có trọng số nhỏ nhất đi qua lát cắt đó thuộc về MST.
  • Tính chất chu trình (Cycle Property): Đối với bất kỳ chu trình nào trong đồ thị, cạnh có trọng số lớn nhất trong chu trình KHÔNG thuộc về MST (giả sử các trọng số là duy nhất).
  • Tính duy nhất: Nếu tất cả các trọng số cạnh là khác biệt, MST là duy nhất. Với các trọng số trùng lặp, có thể có nhiều MST hợp lệ với cùng tổng trọng số.
  • Đồ thị con: MST là một đồ thị con với V-1 cạnh và không có chu trình.

Câu hỏi thường gặp

Cây khung nhỏ nhất (MST) là gì?

Cây khung nhỏ nhất là một tập hợp con các cạnh của một đồ thị vô hướng, có trọng số và liên thông, kết nối tất cả các đỉnh với nhau với tổng trọng số cạnh nhỏ nhất có thể, mà không tạo thành bất kỳ chu trình nào. Một MST có đúng V-1 cạnh cho một đồ thị có V đỉnh.

Sự khác biệt giữa thuật toán Kruskal và Prim là gì?

Thuật toán Kruskal dựa trên cạnh: nó sắp xếp tất cả các cạnh theo trọng số và tham lam thêm các cạnh không tạo ra chu trình, sử dụng cấu trúc dữ liệu Union-Find. Thuật toán Prim dựa trên đỉnh: nó phát triển MST từ một nút bắt đầu bằng cách luôn thêm cạnh rẻ nhất kết nối cây với một đỉnh mới, sử dụng hàng đợi ưu tiên. Cả hai đều tạo ra các MST tối ưu nhưng có thể khác nhau về thứ tự chọn cạnh.

Khi nào nên sử dụng thuật toán Kruskal so với Prim?

Kruskal thường tốt hơn cho các đồ thị thưa (ít cạnh so với nút) với độ phức tạp thời gian O(E log E). Prim tốt hơn cho các đồ thị dày đặc với độ phức tạp thời gian O(E log V) sử dụng heap nhị phân. Đối với các đồ thị rất dày đặc, Prim với Fibonacci heap đạt được O(E + V log V).

Một đồ thị có thể có nhiều MST hợp lệ không?

Có, một đồ thị có thể có nhiều MST hợp lệ nếu có các cạnh có trọng số bằng nhau. Các MST khác nhau sẽ có cùng tổng trọng số nhưng có thể bao gồm các cạnh khác nhau. Kruskal và Prim có thể tạo ra các MST khác nhau cho cùng một đồ thị, nhưng cả hai đều sẽ có cùng tổng trọng số tối thiểu.

Các ứng dụng thực tế của MST là gì?

MST được sử dụng trong thiết kế mạng (tối thiểu hóa chiều dài cáp/sợi quang), bố trí bảng mạch, phân tích cụm, phân đoạn hình ảnh, xây dựng hệ thống phân loại, xấp xỉ các bài toán NP-khó như Bài toán người bán hàng (TSP), và xây dựng mạng lưới đường bộ/đường ống/điện với chi phí tối thiểu.

MST có hoạt động trên đồ thị không liên thông không?

Một MST thực thụ yêu cầu một đồ thị liên thông. Nếu đồ thị không liên thông, các thuật toán sẽ tạo ra một Rừng khung nhỏ nhất — một tập hợp các MST, mỗi cái cho một thành phần liên thông. Máy tính này sẽ cho biết khi đồ thị không liên thông hoàn toàn.

Tài nguyên bổ sung

Tham khảo nội dung, trang hoặc công cụ này như sau:

"Máy tính Cây khung nhỏ nhất" tại https://MiniWebtool.com/vi// từ MiniWebtool, https://MiniWebtool.com/

bởi đội ngũ miniwebtool. Cập nhật: 19 tháng 2, 2026

Bạn cũng có thể thử AI Giải Toán GPT của chúng tôi để giải quyết các vấn đề toán học của bạn thông qua câu hỏi và trả lời bằng ngôn ngữ tự nhiên.

Công cụ nổi bật:

Máy tính tuổiTrình Trích Xuất Ảnh từ VideoCông cụ đổi Pound sang KilogramCông cụ Mã hóa CaesarCông cụ chuyển đổi kg sang lbsMáy tính giảm giá phần trămMáy tính thương và số dưTrình Tạo Mã MorseCông cụ chuyển đổi chữ số La MãĐảo ngược văn bảnMáy tính phân số tối giảnCông cụ chuyển đổi nhị phân sang thập phânTrình tạo số nguyên ngẫu nhiênCông cụ đếm hàngXóa dấu cáchMáy tính thập phân sang phân sốTrình tạo chuỗi ngẫu nhiênCon số may mắn của tôi là gì?Máy tính Phân tích Thừa số Nguyên tốTrình tạo tên ngẫu nhiênMáy tính xác suất xúc xắcCông cụ chia ảnhBộ chuyển đổi FPSmáy-tính-số-mũ-độ-chính-xác-caoCông cụ chuyển đổi cm sang feet và inchCông cụ chuyển đổi kPa sang psiBộ chuyển đổi Feet và Inch sang CmBộ chuyển đổi thập phân sang nhị phânTrình tạo ngày sinh ngẫu nhiênMáy tính căn bậc haiTrình tạo mê cungMáy phát động vật ngẫu nhiênTrình tạo số xổ sốMáy tính So sánh Phân sốSắp xếp sốMáy tính thời gianCông cụ tạo Sự thật hay Thách đốMáy tính nhị phânCông cụ tạo nhóm ngẫu nhiênMáy tính xác suấtMáy tính giai thừaParaphraser AIMáy tính HEXBộ lặp MP3Máy tính Cạnh huyềnTrình Tạo Màu Ngẫu NhiênTrình tạo đồ vật ngẫu nhiênCông cụ chuyển đổi inch sang centimetBộ giải mã Base64Máy tính Ước số chung lớn nhấtMáy tính ngày trong năm - Hôm nay là ngày thứ mấy trong năm📅 Máy tính ngàySắp xếp theo thứ tự bảng chữ cáiBộ Giải Mã Mã MorseCông cụ chuyển đổi phân số thành hỗn sốTrình tạo Hash MD5Bộ chuyển đổi hex sang thập phânBộ Chuyển Đổi Nhị PhânTrình chuyển đổi SRT sang TXTMáy Tính Giờ Làm ViệcTrình trích xuất âm thanhBộ chuyển đổi HEXMáy tính hoán vịMáy tính ModuloMáy tính One Rep Max (1RM)Đây có phải là Số Nguyên Tố?Bộ chuyển đổi Thập phân sang Thập lục phânTrình tạo PIN ngẫu nhiênBộ chuyển đổi Nhị phân sang HexBộ chuyển đổi RGB sang HexChọn tên ngẫu nhiênMáy tính tương hợp tình yêuTrình tạo oẳn tù tìMáy tính độ lệch chuẩn - Độ chính xác caoCông cụ chuyển đổi hệ thập lục phân sang nhị phânCông cụ chuyển đổi thập phân sang bát phântra-cứu-địa-chỉ-macMáy tính Tổngchuyển đổi từ sang số điện thoạiCông cụ chuyển đổi bát phân sang thập phânCông cụ chuyển đổi centimet sang inchMáy tính Cung Mặt trời, Mặt trăng & Cung mọc 🌞🌙✨AI Trình thêm dấu câuBộ chuyển đổi hệ cơ sốBộ chọn màu hình ảnhBộ nén hình ảnhCông cụ chuyển đổi bát phân sang nhị phânTrình nén VideoTung đồng xuĐiều chỉnh tốc độ videoDanh sách các số nguyên tốGhép VideoMáy tính Log Base 10Máy tính LogaritMáy tính số thiên thầnMáy tính trung bìnhBộ Chuyển Đổi Mã Nhị Phân Sang Mã XámCông cụ chuyển đổi pound sang gamMáy tính BitwiseMáy tính Hoán vị lệch (Giai thừa phụ)Trình tạo Số CatalanTrình xác thực dãy bậc đồ thịMáy tính Cây khung nhỏ nhấtMáy tính Đường đi Ngắn nhất DijkstraTrình tạo Ma phươngMáy tính Số Hạnh phúcMáy tính Phỏng đoán CollatzMáy tính Độ congMáy tính Bán kính Hội tụMáy tính Phân tích LU Ma trậnMáy tính Phép chiếu VectorMáy tính Gram-SchmidtMáy tính Phương trình Hình cầuMáy tính khoảng cách từ điểm đến mặt phẳngMáy tính Trực tâm Tam giácMáy tính Trọng tâm Tam giácMáy tính Công thức Dây giàyMáy tính Phân số liên tụcMáy tính Nghịch đảo Nhân theo Mô-đunMáy tính Thuật toán Euclid Mở rộngMáy tính Hàm Phi EulerMáy tính Định lý Số dư Trung QuốcCông cụ tạo Biểu đồ Venn (3 Tập hợp)Máy tính lý thuyết tập hợpCông cụ tạo bảng chân trịCông cụ chuyển đổi cân nặng người sang kiếnMáy tính Calo cho MèoMáy tính tiết kiệm bóng đènMáy tính Chi phí TắmMáy tính chi phí điện đào BitcoinMáy tính Giá trị Giấy vệ sinhTra cứu ID người dùng InstagramMáy tính Quãng đường Bàn phímTrình tạo Bingo từ thông dụngMáy tính Xác suất Ngày nghỉ ốmMáy tính lương thực tế theo giờMáy tính Cà phê vs. Giấc ngủMáy tính thời gian trả lời emailMáy tính FIRE - Tự do Tài chính, Nghỉ hưu sớmMáy tính thời gian lãng phí đi làmBộ đếm Chi phí Cuộc họpMáy tính lương trong nhà vệ sinhTrình tạo KakuroTrình tạo KenKen (Calcudoku)trình-tạo-nonogram-picrossGiải và luyện trò chơi 24Tạo và giải SudokuMáy tính khay phô maiMáy tính đài phun sô cô laMáy tính ABV CocktailMáy tính khẩu phần mì SpaghettiMáy tính thời gian làm lạnh biaMáy tính Taco BarMáy tính BBQMáy tính quá liều CaffeineCông cụ lập kế hoạch tiệc pizzaMáy tính rượu tiệc cướiMáy tính Nhà gạch LegoMáy tính Lấp đầy Phòng Bỏng ngôMáy tính va chạm đồng xu rơiMáy tính rơi xuyên Trái đấtMáy tính bức xạ chuốiMáy tính năng lượng Chuột HamsterMáy tính Tỷ lệ Lỗi Dịch chuyển Tức thờiMáy tính nấu gà bằng năng lượng động năngMáy tính lực nâng bóng bay HeliMáy tính Thời gian Sống sót ZombieTrình Kiểm Tra Kích Thước Thu Thập GooglebotMáy tính tỷ lệ bãi đỗ xeMáy tính Cây thông NoelMáy Tính Ngày Tận Thế Ma Cà RồngMáy tính giá trị PizzaMáy tính Quầy nước chanhTrình tạo tiểu bang Mỹ ngẫu nhiênTrình tạo lý do ngẫu nhiênTrình tạo hoạt động ngẫu nhiênTrình tạo công thức cocktail ngẫu nhiênCông cụ chọn phim ngẫu nhiênTrình tạo tên miền ngẫu nhiênTrình tạo siêu năng lực ngẫu nhiênTrình tạo Haiku ngẫu nhiênTrình tạo lời nhắc viết ngẫu nhiênTrình tạo IMEI Ngẫu nhiênTrình tạo chân dung người dùng ngẫu nhiênTrình tạo địa chỉ giả ngẫu nhiênTrình tạo số cổng ngẫu nhiênTrình tạo NanoID ngẫu nhiênMáy tính tuổi thọ pinMáy tính độ rộng đường mạch PCBMáy tính sụt ápMáy tính định luật OhmMáy tính mã màu điện trởTrình tạo chuyển hướng HtaccessCông cụ tối ưu SVGCông cụ tạo faviconCông cụ tạo biểu thức CrontabTrình định dạng SQLCông cụ chuyển đổi cURL sang JSONBộ giải mã JWTCông cụ chuyển đổi JSON sang YAMLMáy tính Chuyển đổi MenCông cụ chuyển đổi kích thước khuôn bánhMáy tính độ ẩm bột nhàomáy-tính-tỷ-lệ-bánh-mìMáy tính kích thước thêu chữ thậpMáy tính vảiMáy tính sợi lenMáy tính nước muối và độ mặnMáy tính tỷ lệ pha cà phêMáy tính ABV bia thủ côngMáy tính sáp và tinh dầu thơm nếnMáy tính xút làm xà phòng (SAP)Máy tính kích thước in và độ phân giải (DPI/PPI)Máy tính Golden Hour và Blue HourMáy tính độ sâu trường ảnh (DoF)Máy tính khoảng cách trồng câyMáy tính Chuyển đổi Tỷ lệ Mô hìnhMáy tính vật liệu nền bể cáMáy tính thể tích và mật độ cá bểQuay vòng quayĐổ xúc xắcQuả cầu Thần kỳ 8Trình tạo bài tây ngẫu nhiênCông cụ tạo địa chỉ IP ngẫu nhiênTrình tạo thời gian ngẫu nhiênTrình tạo ngày ngẫu nhiênCông cụ tạo tọa độ ngẫu nhiênCông cụ tạo User-Agent ngẫu nhiênTrình tạo thẻ tín dụng ngẫu nhiênTrình tạo JSON ngẫu nhiênTrình tạo quốc gia ngẫu nhiênCông cụ tạo bảng màu ngẫu nhiênCông cụ tạo Emoji ngẫu nhiênCông cụ tạo bữa ăn ngẫu nhiênTrình tạo nhánh giải đấu ngẫu nhiênCông Cụ Tạo Phân Phối GaussMáy tính Giá trị PipMáy tính Lãi kép Hàng ngàyMáy tính Chiến lược MartingaleMáy tính Tiêu chí KellyMáy tính Stop Loss & Take ProfitMáy tính mở rộng Fibonaccimáy-tính-điểm-xoayMáy tính đòn bẩy tiền điện tửBộ chuyển đổi Satoshi sang Đô laMáy Tính Chênh Lệch Giá Tiền Điện TửMáy tính tổn thất tạm thờiMáy Tính Lợi Nhuận Quyền ChọnMáy Tính Biến Động Ngầm ĐịnhMáy tính Greek Quyền chọnMáy tính Định giá Quyền chọn Black-ScholesMáy tính rủi ro phá sảnMáy tính lợi nhuận bán khốngMáy tính Margin CallMáy Tính Kích Thước Vị Thếmáy tính giá trung bình cổ phiếuCông cụ xóa ký tự vô hìnhCông cụ Chuyển đổi Văn bản sang Danh sách SQLCông cụ trích xuất cột văn bảnMáy tính sự khác biệt danh sáchCông cụ tạo văn bản ZalgoCông cụ tạo nghệ thuật ASCIICông cụ tạo văn bản vô hình