摘要： 克魯斯卡爾算法(Kruskal's algorithm)是兩個(gè)經(jīng)典的最小生成樹算法的較為簡單理解的一個(gè)。 這里面充分體現(xiàn)了貪心算法的精髓。 大致的流程可以用一個(gè)圖來表示。這里的圖的選擇借用了Wikipedia上的那個(gè)。非常清晰且直觀。 首先第一步，我們有一張圖，有若干點(diǎn)和邊 如下圖所示： . . . . . . 第一步我們要做的事情就是將所有的邊的長度排序，用排序的結(jié)果作為我們選擇邊的依據(jù)。 這里再次體現(xiàn)了貪心算法的思想。資源排序，對局部最優(yōu)的資源進(jìn)行選擇。 排序完成后，我們率先選擇了邊AD。 這樣我們的圖就變成了 . . . . . . 第二步，在... 閱讀全文

摘要： 用Prim算法來求出最小生成樹的過程Prim算法的描述：設(shè)圖G =（V，E），其生成樹的頂點(diǎn)集合為U。 ①、把v0放入U(xiǎn)。 ②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權(quán)值的邊，加入生成樹。 ③、把②找到的邊的v加入U(xiǎn)集合。如果U集合已有n個(gè)元素，則結(jié)束，否則繼續(xù)執(zhí)行②。 其算法的時(shí)間復(fù)雜度為O（|E|*log|V|） 第2條是什么意思呢？ 它的意思是從剩下的所有的邊中找出最小的邊，但是這個(gè)邊是有要求的，也就是必須是與剛剛加入的頂點(diǎn)相通的權(quán)值最小的邊。 如果還是不懂的話，就看看上面的圖吧！ 閱讀全文