有人提出這樣的一種從圖G中頂點u開始構(gòu)造最小生成樹的方法：
假設(shè)G=（V，E）是一個具有n個頂點的帶權(quán)連通無向圖，T=（U，TE）是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，則由G構(gòu)造從起始頂點u出發(fā)的最小生成樹T的步驟如下：
（1）初始化U={u}。以u到其他頂點的所有邊為候選邊。
（2）重復(fù)以下步驟n-1次，使得其他n-1個頂點被加入到U中。
從候選邊中挑選權(quán)值最小的邊加入到TE，設(shè)該邊在V-U中的頂點是v，將v加入U中。
考查頂點v，將v與V-U頂點集中的所有邊作為新的候選邊。
若此方法求得的T是最小生成樹，請予以證明。若不能求得最小邊，請舉出反例。
您可能感興趣的試卷
你可能感興趣的試題
A.{75，65，30，15，25，45，20，10}
B.{75，65，45，10，30，25，20，15}
C.{75，45，65，30，15，25，20，10}
D.{75，45，65，10，25，30，20，15}
用某種排序方法對數(shù)據(jù)序列{24，88，21，48，15，27，69，35，20}進(jìn)行遞增排序，元素序列的變化情況如下：
（1）{24，88，21，48，15，27，69，35，20}
（2）{20，15，21，24，48，27，69，35，88}
（3）{15，20，21，24，35，27，48，69，88}
（4）{15，20，21，24，27，35，48，69，88}
則所采用的排序方法是（）。
A.快速排序
B.簡單選擇排序
C.直接插入排序
D.歸并排序
A.O（n）
B.O（nlog2n）
C.O（n2）
D.O（√n）
最新試題
若三維數(shù)組a［4］［5］［6］的基地址是100，每個元素占用2個存儲單元，則數(shù)組a中最后一個元素的存儲地址是（）。
已知二叉樹用二叉鏈表存儲，則若實現(xiàn)二叉樹實現(xiàn)左右子樹交換，可以借助改寫（）遍歷算法實現(xiàn)。
在中序遍歷非遞歸算法中，在進(jìn)入子樹進(jìn)行訪問前，需要在自定義棧中保存（）
已知帶頭結(jié)點的鏈隊列指針Q，則該隊列做新元素結(jié)點s進(jìn)隊操作的語句是（）
二叉樹的二叉鏈表類型定義如下：閱讀下列算法，并回答問題：（1）該算法的功能是什么？（2）以下算法功能是否等價于上面的算法？
則該隊列為空隊列的條件為（）
只要無向圖中有權(quán)重相同的邊，其最小生成樹就不可能唯一。
在打印楊輝三角形前N行的算法中，需要申請一個N*N的二維數(shù)組存放楊輝三角形N行數(shù)據(jù)。
設(shè)二叉樹采用二叉鏈表方式存儲，root指向根結(jié)點，r所指結(jié)點為二叉樹中任一給定的結(jié)點。則可以通過改寫（）算法，求出從根結(jié)點到結(jié)點r之間的路徑。
一棵二叉樹的先序序列是：CEDBA，中序序列是：DEBAC ，則該二叉樹的后序序列是（）