1樓：趙馮平
1.做9輪冒泡，把最大的9條邊「冒泡」到最後位置，這時前面n-1條邊是無序的，但其權值小於後面9條邊，而後面9條邊是按權值從小到大排序的。進行了9*n次冒泡操作，複雜度O(n)。
生成的邊的序列成為A，A的每個元素包含邊的起點、終點及權值。
2. 類似克魯斯卡爾演算法，按第1步生成的順序A中，從頭到尾取n-1條邊，構造生成樹即可。克魯斯卡爾演算法複雜度為O(n)。
選邊方法要稍作改進： 若正好取了前n-1條邊，那肯定是最小生成樹。 若生成序列前n-1條邊中出現不能使用的邊(u,v)，即加入這條邊之前，結點u、v已在同一集合A中，則需要在生成集合A的邊中查詢是否有權值大於(u,v)邊的權值的邊，若有則用(u,v)邊替換它，這種替換操作最多發生9次。
若要取到後面的9條邊，由於後面的邊是排序的，按克魯斯卡爾演算法原理，所以生成的樹肯定是最小生成樹。
克魯斯卡爾演算法每次選邊的時間複雜度並非O(1)。
更正：1.做9輪冒泡，把最大的9條邊「冒泡」到最後位置，這時前面n-1條邊是無序的，但其權值小於後面9條邊，而後面9條邊是按權值從小到大排序的。
進行了9*n次冒泡操作，複雜度O(n)。生成的邊的序列成為A，A的每個元素包含邊的起點、終點及權值。
2.從A中選n-1條邊，構成生成圖G1。
3.對G1進行深度優先搜尋，如果G1連通，則G1就是最小生成樹；
5.從A序列剩下的9條邊中，按克魯斯卡爾演算法原理，完成構造最小生成樹的任務。
2樓：
可用克魯斯卡爾演算法，其中對邊排序的步驟，如果使用比較排序法（如快速排序），則複雜度為O(nlogn)，為了達到O(n)複雜度，需要使用《程式設計珠璣》第一章中介紹的點陣圖排序演算法(bitsort)
3樓：CuKing
暴力即可.
先隨便加,加到成環為止,然後找到環上最大的邊刪掉,反覆.
因為只有n+8條邊,最多最多也就是把整個圖遍歷9次,所以複雜度是O(9n+n+8)=O(n)的
乙個頂點三條稜的立體有哪些，與頂點個數n的關係是如何
乘著歌聲的翅膀 5月21日補充 如果題主想問n取不同值的時候，滿足乙個頂點為三條稜的多面體有多少種 同坯的算一種 的話。難算，現在沒有好的公式表達。但可以肯定的是n為奇數時，a n 0。之前答案講過，因為這類多面體的對偶多面體三角面多面體，所以如果你題目裡的這個n指的是面的話，這個問題就等價於n個頂...
乙個有n條邊的簡單圖最多有幾個三角形
好地方bug 猹猹 大佬的回答很完善了，我來個簡單漸進版本的。我們設函式 表示乙個有 條邊的圖的三角形數量的最大值。引理 乙個有 條邊的圖，證明 首先我們考慮這個圖是個完全圖，即存在 0 eeimg 1 使得 這個時候，三角形的數量 我們假設 是最小的正整數使得 令 不難證明 否則有 這與 是最小的...
怎樣證明兩個小正n邊形蓋不住乙個大正n邊形？
何睿杰 兩個小圓無法覆蓋乙個大圓。可知兩個小的正n邊形無法覆蓋大的正n邊形。兩個小圓無法覆蓋大圓 可以用三角形兩邊之差小於第三邊證明，始終存在大圓上存在一點，不被兩圓中任何乙個覆蓋。 拓唐 這題有個簡單一些的思路，我們只需證明 a 任意兩個小正三角形無法覆蓋乙個單位正三角形。b 任意正n邊形可以在內...