『壹』 最短路和最小生成樹有的區別是什麼啊
終於見到個數據結構的問題.
最小生成樹是從一節點到另一節點最少的邊集.最短路是帶權路徑,權值最小.
『貳』 最小生成樹和最短路的區別
不一定
比如5個點連了一圈邊 5個邊中有四個長度1，一個長度2
那麼最小生成樹是選4個長度為1的邊
但是長度為2的邊連接的兩個點之間最短路是2，沒必要繞一圈
『叄』 生成樹的標准有哪些各有什麼異同
一 區別
最小生成樹能夠保證整個拓撲圖的所有路徑之和最小，但不能保證任意兩點之間是最短路徑。
最短路徑是從一點出發，到達目的地的路徑最小。
二 實現方法
最小生成樹
最小生成樹有兩種演算法來得到：Prims演算法和Kruskal演算法。
Kruskal演算法：根據邊的加權值以遞增的方式，一次找出加權值最低的邊來構建最小生成樹，而且規定：每次添加的邊不能造成生成樹有迴路，知道找到N-1個邊為止。
Prims演算法：以每次加入一個的臨界邊來建立最小生成樹，直到找到N-1個邊為止。其規則為：以開始時生成樹的集合（集合U）為起始的定點，然後找出與生成樹集合鄰接的邊（集合V）中，加權值最小的邊來建立生成樹，為了確定新加入的邊不會造成迴路，所以每一個新加入的邊，只允許有一個頂點在生成樹集合中，重復執行此步驟，直到找到N-1個邊為止。
2 最短路徑
演算法描述
(這里描述的是從節點1開始到各點的dijkstra演算法，其中Wa->b表示a->b的邊的權值，d(i)即為最短路徑值)
1． 置集合S={2,3,n}, 數組d(1)=0, d(i)=W1->i(1,i之間存在邊) or +無窮大(1.i之間不存在邊)
2． 在S中，令d(j)=min{d(i),i屬於S}，令S=S-{j}，若S為空集則演算法結束，否則轉3
3． 對全部i屬於S,如果存在邊j->i，那麼置d(i)=min{d(i), d(j)+Wj->i}，轉2
Dijkstra演算法思想為：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將 加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。
演算法具體步驟
（1）初始時，S只包含源點，即S=，v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權（若v與u有邊）或 ∞(若u不是v的出邊鄰接點）。
（2）從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。
（3）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u（u U）的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改後的距離值為頂點k的距離加上邊上的權。
（4）重復步驟（2）和（3）直到所有頂點都包含在S中。
復雜度分析
Dijkstra 演算法的時間復雜度為O(n^2)空間復雜度取決於存儲方式，鄰接矩陣為O(n^2)
『肆』 最小生成樹的兩種演算法
主要有兩個：
1.普里姆（Prim)演算法
特點：時間復雜度為O(n2).適合於求邊稠密的最小生成樹。
2.克魯斯卡爾（Kruskal)演算法
特點：時間復雜度為O(eloge)(e為網中邊數），適合於求稀疏的網的最小生成樹。
『伍』 最小生成樹與最短路徑的區別
最小生成樹是用和最少的邊集將一個圖連成任意2點可達，並且這個邊集的總長度最小。最短路徑是一個圖中2個點的最短距離。完全不是一個概念。
那也不一樣啊，一點到其餘各點的路徑和最小，就是一點到其它點的最短路徑和。差的太遠了。
比如這樣一個圖(邊權已標出)
******4
*****v--v
****5 \ / 3
*******v
****2 / \ 4
*****v v
最小生成樹為
****v--v
******/
*****v
****/ \
***v v
總長為4+3+2+4=13
中間那個點到各點的最短路徑為5+2+3+4=14
顯然不一樣啊，反例太多了，舉了一種。
『陸』 最短路演算法和最小生成樹演算法有什麼區別
兩個演算法沒有什麼太多的聯系，只能說是想法類似，都用了一定程度的貪心思維。
最短路是要求一點到另外的點的最短路徑，只要最短的長度到達就好，除了出發點和終點外一概不管。如果不求一點到所有點的最短路，甚至可以不管所有點是否都聯通。
最小生成樹則要保證第一所有點都是聯通的，不然就稱不上是樹了，而後保證樹的邊長度之和最小。
『柒』 最小生成樹兩種演算法有何區別
主要有兩個：
1.普里姆（Prim)演算法
特點：時間復雜度為O(n2).適合於求邊稠密的最小生成樹。
2.克魯斯卡爾（Kruskal)演算法
特點：時間復雜度為O(eloge)(e為網中邊數），適合於求稀疏的網的最小生成樹。
『捌』 最小生成樹和哈夫曼樹有什麼區別
最短路徑和最小生成樹是不同的概念.
最短路徑是對於一個圖的兩個結點而言的.在一個圖中,結點A通過某些結點和邊可以走到結點B,那這些結點和邊就組成一條A到B的路徑,A到B的最短路徑就是A到B的所有路徑中邊權值總和最小的那一條（或多條）.
最小生成樹是對於一個圖本身而言的.對於一個有n個結點的無向連通圖（邊沒有方向,任意兩點之間都存在路徑可以到達）,必然可以去掉某些邊,使得最終剩下n-1條邊,並且n個結點仍然是連通的,這n個結點和n-1條邊組成了原圖的一個生成樹,而最小生成樹就是所有可能的生成樹中n-1條邊的權值總和最小的那一個（或多個）.
最短路徑常用演算法有：floyd,dijkstra,SPFA,A*等
最小生成樹常用演算法有：prim,kruskal