Giải thuật Kruskal hoạt động như thế nào trong lý thuyết đồ thị và độ phức tạp thời gian của nó là bao nhiêu?

Question

Accepted Answer

Giải thuật Kruskal là một giải thuật tham lam (greedy algorithm) dùng để tìm cây khung nhỏ nhất (minimum spanning tree) trong một đồ thị. Tuy nhiên, khác với một số giải thuật khác, đồ thị trong giải thuật Kruskal không bắt buộc phải liên thông.
Độ phức tạp thời gian: O(|E|log|V|) trong đó |E| là số lượng cạnh và |V| là số lượng đỉnh của đồ thị.

Giải thuật Kruskal hoạt động như thế nào trong lý thuyết đồ thị và độ phức tạp thời gian của nó là bao nhiêu?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi Data Structures liên quan cùng chủ đề