有人提出這樣的一種從圖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）
最新試題
對以下幾個關(guān)鍵字的序列進行快速排序，以第一個元素為基準，一次劃分效果不好的是（）
單鏈表類型定義如下：用不帶頭結(jié)點的單鏈表存儲待排數(shù)據(jù)，鏈表頭指針為head。下列直接選擇排序算法對鏈表按升序進行排序，請?zhí)顚戇m當內(nèi)容使算法完整。
順序表中有10個數(shù)據(jù)元素，若第一個元素的存儲地址是1000，則最后一個元素地址是1036，第5個元素的地址是（）
只要無向圖中有權(quán)重相同的邊，其最小生成樹就不可能唯一。
已知帶頭結(jié)點的鏈隊列指針Q，則該隊列做新元素結(jié)點s進隊操作的語句是（）
對關(guān)鍵字{28，16，32，12，60，2，5，72}進行快速排序，第一趟以28為樞軸產(chǎn)生的劃分結(jié)果為（）
通常將（）作為衡量一個查找算法效率優(yōu)劣的標準。
在中序遍歷非遞歸算法中，在進入子樹進行訪問前，需要在自定義棧中保存（）
則該隊列中元素個數(shù)為（）
實現(xiàn)二分查找的遞歸章法如下，在相應(yīng)位置填寫適當?shù)膬?nèi)容使算法完整。