有人提出這樣的一種從圖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）重復以下步驟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}進行遞增排序，元素序列的變化情況如下：
（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）
最新試題
一棵二叉樹的先序序列是：CEDBA，中序序列是：DEBAC ，則該二叉樹的后序序列是（）
當需要用一個形式參數(shù)直接改變對應(yīng)實參的值時，該形式參數(shù)應(yīng)說明為（）
一棵二叉樹的后序序列是：CBEFDA，中序序列是：CBAEDF，則該二叉樹的先序序列是（）
單鏈表類型定義如下：設(shè)計算法在帶頭結(jié)點的單鏈表L中刪除數(shù)據(jù)值最小的結(jié)點（設(shè)鏈表中各結(jié)點數(shù)據(jù)值均不相同）。函數(shù)的原型為：void f34（LinkList L）
若三維數(shù)組a［4］［5］［6］的基地址是100，每個元素占用2個存儲單元，則數(shù)組a中最后一個元素的存儲地址是（）。
順序表中有10個數(shù)據(jù)元素，若第一個元素的存儲地址是1000，則最后一個元素地址是1036，第5個元素的地址是（）
在打印楊輝三角形前N行的算法中，需要申請一個N*N的二維數(shù)組存放楊輝三角形N行數(shù)據(jù)。
非空單鏈表結(jié)點結(jié)構(gòu)為[data，next]，若指針p所指結(jié)點是尾結(jié)點，則（）表達式為真。
已知某二叉樹的后序遍歷序列是CEFDBA，中序遍歷序列是CBEDFA。與該二叉樹對應(yīng)的樹或森林中，葉子的數(shù)目是（）個。
則該隊列中元素個數(shù)為（）