Minimum Spanning Tree (MST) problem 屬於 polynomial-time solvable 類別。這意味著存在多項式時間內的算法可以找到一個給定加權無向圖的最小生成樹。典型的算法包括克魯斯克爾算法（Kruskal's Algorithm）和普里姆算法（Prim's Algorithm），它們都能在多項式時間內解決 MST 問題。這些算法的時間複雜度通常與圖中的邊和頂點數量有關，例如，使用適當的數據結構（如斐波那契堆）的普里姆算法的時間複雜度可以達到 O(E+VlogV)，其中 E 是邊的數量，V 是頂點的數量。这表明 MST 问题可以有效地在多项式时间内解决。
阿摩線上測驗
登入