有人提出這樣的一種從圖G中頂點(diǎn)u開始構(gòu)造最小生成樹的方法：
假設(shè)G=（V，E）是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向圖，T=（U，TE）是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，則由G構(gòu)造從起始頂點(diǎn)u出發(fā)的最小生成樹T的步驟如下：
（1）初始化U={u}。以u(píng)到其他頂點(diǎn)的所有邊為候選邊。
（2）重復(fù)以下步驟n-1次，使得其他n-1個(gè)頂點(diǎn)被加入到U中。
從候選邊中挑選權(quán)值最小的邊加入到TE，設(shè)該邊在V-U中的頂點(diǎn)是v，將v加入U(xiǎn)中。
考查頂點(diǎn)v，將v與V-U頂點(diǎn)集中的所有邊作為新的候選邊。
若此方法求得的T是最小生成樹，請(qǐng)予以證明。若不能求得最小邊，請(qǐng)舉出反例。
您可能感興趣的試卷
你可能感興趣的試題
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}
用某種排序方法對(duì)數(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.簡(jiǎn)單選擇排序
C.直接插入排序
D.歸并排序
A.O（n）
B.O（nlog2n）
C.O（n2）
D.O（√n）
最新試題
數(shù)據(jù)元素在計(jì)算機(jī)的存儲(chǔ)映像包括（）
則該隊(duì)列中元素個(gè)數(shù)為（）
已知帶頭結(jié)點(diǎn)的鏈隊(duì)列指針Q，則該隊(duì)列做新元素結(jié)點(diǎn)s進(jìn)隊(duì)操作的語句是（）
當(dāng)需要用一個(gè)形式參數(shù)直接改變對(duì)應(yīng)實(shí)參的值時(shí)，該形式參數(shù)應(yīng)說明為（）
某圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，則從6號(hào)點(diǎn)出發(fā)，深度優(yōu)先遍歷的序列是（）
非空單鏈表結(jié)點(diǎn)結(jié)構(gòu)為[data，next]，若指針p所指結(jié)點(diǎn)是尾結(jié)點(diǎn)，則（）表達(dá)式為真。
設(shè)二叉樹采用二叉鏈表方式存儲(chǔ)，root指向根結(jié)點(diǎn)，r所指結(jié)點(diǎn)為二叉樹中任一給定的結(jié)點(diǎn)。則可以通過改寫（）算法，求出從根結(jié)點(diǎn)到結(jié)點(diǎn)r之間的路徑。
一棵二叉樹的先序序列是：CEDBA，中序序列是：DEBAC ，則該二叉樹的后序序列是（）
頭指針為L的帶頭結(jié)點(diǎn)的雙循環(huán)鏈表，結(jié)點(diǎn)的前趨指針域?yàn)閜rior，后繼指針域?yàn)閚ext，判斷該鏈表為空的條件是（）。
則該隊(duì)列為滿隊(duì)列的條件為（）（采用少用一個(gè)空間的方法）