图所示是一个无向带权图,请分别按Prim算法和Kruskal算法求最小生成树. 请对下图的无向带权图：1写出它的邻接矩阵，并按普里姆算法求其...
\u5982\u56fe\u6240\u793a\u4e3a\u4e00\u4e2a\u65e0\u5411\u5e26\u6743\u56fe,\u8bf7\u5206\u522b\u6309\u7167Prim\u7b97\u6cd5\u548cKruskal\u7b97\u6cd5\u6c42\u6700\u5c0f\u751f\u6210\u6811\u6309\u7167prim\u662f\uff1a\uff08\u4ece\u8d77\u70b9\u5230\u7ec8\u70b9\u7684\u8fb9\uff09
46\uff0c45\uff0c51\uff0c63\uff0c12\uff0c32
\u6309\u7167kruskal\u662f\uff1a
46\uff0c15\uff0c45\uff0c63\uff0c12\uff0c32
1. \u90bb\u63a5\u77e9\u9635
A B C D E F G H
A 0 4 3 - - - - -
B 4 0 5 5 9 - - -
C 3 5 0 5 - - - 5
D - 5 5 0 7 6 5 4
E - 9 - 7 0 3 - -
F - - - 6 3 0 2 -
G - - - 5 - 2 0 6
H - - 5 4 - - 6 0
2.\u90bb\u63a5\u8868
A| B C
B| A C D E
C| A B D H
D| B C E F G H
E| B D F
F| E D G
G| D F H
H| C D G
3.\u666e\u91cc\u59c6\u7b97\u6cd5\u6c42\u5176\u6700\u5c0f\u751f\u6210\u6811
\u9009\u62e9\u539f\u70b9\u4e3aA
1. A-C
2. A-B
|
C
3. A-B
|
C-D
4. A-B
|
C-D-H
5. A-B
|
C-D-H
|
G
7. A-B
|
C-D-H
|
G
|
F-E
\u603b\u8ddd\u79bb\uff1a26
4.\u514b\u9c81\u65af\u5361\u5c14\u7b97\u6cd5\u6c42\u5176\u6700\u5c0f\u751f\u6210\u6811
1. E-F
2. E-F
A-C
3. E-F
A-C
D-H
4. E-F
D-H
B-A-C
5. B-A-C
G-D-H
E-F
6. B-A-C-H-D-G
E-F
7. B-A-C-H-D-G-F-E
\u603b\u8ddd\u79bb\uff1a26
\u5e0c\u671b\u80fd\u5e2e\u5230\u4f60
•普里姆（Prim）算法
基本思想
假设N=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是所求的最小生成树，其中U是T的顶点集，TE是T的边集。
（1）初始U={u0}(u0∈V),TE=φ；
（2）在所有u∈U,v∈V-U的边中选一条代价最小的边（u0，v0）并入集合TE，同时将v0并入U；
（3）重复（2），直到U=V为止。
此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最小生成树。
克鲁斯卡尔（Kruskal）算法
基本思想
假设N=(V,E)是一个具有n个顶点的连通网，
（1）将n个顶点看成n个集合；
（2）按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；
（3）重复（2），直到所有的顶点都在同一个顶点集合内。
注意：1.最小生成树不唯一。
2.该图从节点最小开始。
绛旓細•鏅噷濮嗭紙Prim锛夌畻娉 鍩烘湰鎬濇兂 鍋囪N=(V,E)鏄竴涓鍏锋湁n涓《鐐圭殑杩為氱綉锛孴=(U,TE)鏄墍姹傜殑鏈灏忕敓鎴愭爲锛屽叾涓璘鏄疶鐨勯《鐐归泦锛孴E鏄疶鐨勮竟闆嗐傦紙1锛夊垵濮婾={u0}(u0鈭圴),TE=蠁锛涳紙2锛夊湪鎵鏈塽鈭圲,v鈭圴-U鐨勮竟涓変竴鏉′唬浠锋渶灏忕殑杈癸紙u0锛寁0锛夊苟鍏ラ泦鍚圱E锛屽悓鏃跺皢v0骞跺叆U锛涳紙3锛夐噸...
绛旓細1. 閭绘帴鐭╅樀 A B C D E F G H A 0 4 3 - - - - - B 4 0 5 5 9 - - - C 3 5 0 5 - - - 5 D - 5 5 0 7 6 5 4 E - 9 - 7 0 3 - - F - - - 6 3 0 2 - G ...
绛旓細1.閫2->4锛屾渶灏忥紝鏉冨间负1锛2锛4->5 鏉冨间负2 锛3锛4->3;4:2->1;5:5->7;6:4->6;灏卞緱鍒颁簡鏈灏忕敓鎴愭爲銆
绛旓細鑷繁鎸変笅闈㈢殑鍏堝悗杩囩▼鐢诲浘鍗虫槸鐢熸垚杩囩▼锛涜鏄庯紙i,j锛夋槸涓鏉¤繛鎺ラ《鐐筰鍜宩鐨勪竴鏉¤竟锛涙櫘鍒╁锛圥rim)绠楁硶锛氫粠椤剁偣0寮濮嬫瀯閫 锛0,1锛夛紝锛0,2锛夛紝锛1,2锛夛紝锛2,5锛夛紝锛5,4锛夊厠椴佹柉鍗″皵绠楁硶锛氾紙0,1锛夛紝锛0,2锛夛紝锛1,2锛夛紝锛4,5锛夛紝锛2,5锛
绛旓細1銆佸厛鎶婅璁茶В鐨勫浘鍦ㄤ笅闈㈠睍绀轰竴涓嬶紝鍏堢湅涓涓嬶紱2.鐒跺悗鍦ㄥ浘涓殑閭绘帴鐐圭殑鍊肩殑鑼冨洿鐢诲嚭閭绘帴琛ㄧ殑琛ㄥご銆3.鏍规嵁涓婁竴姝ョ敾鍑虹殑琛ㄥご鍒嗘瀽涓庡叾鐩歌繛鐨勭偣锛岃繖閲岄摼琛ㄤ箣涓悗闈㈡湁3涓锛4.鍦ㄩ摼琛ㄤ腑绗竴涓鍐欑浉杩炵偣鐨勯《鐐瑰硷紝绗簩涓涓啓鏉冨硷紱5銆佹牴鎹笂杩扮殑鏂瑰紡锛屼緷娆℃妸鍚庨潰鏁板瓧鐨勯摼琛ㄥ啓涓嬫潵锛屾棤鍚戝甫鏉冨浘鐨...
绛旓細V1V2V3V4V5鏈灏忎唬浠锋槸2 + 5 + 3 + 6 = 16
绛旓細1 2009-12-23 璇峰涓嬪浘鐨勬棤鍚戝甫鏉冨浘:1鍐欏嚭瀹冪殑閭绘帴鐭╅樀,骞舵寜鏅噷濮嗙畻娉曟眰鍏... 106 2010-12-09 瀵瑰浘2鎵绀虹殑鏃犲悜甯︽潈鍥,鐢ㄦ櫘閲屽绠楁硶鎴栧厠椴佹柉鍗″皵绠楁硶姹傚叾鏈灏... 6 2012-12-17 5. 瀵瑰涓鍥炬墍绀鐨勬棤鍚戝甫鏉冨浘,鎸夌収Kruskal绠楁硶姹傚嚭鏈... 1 2014-06-14 宸茬煡甯︽潈鏈鍚戝浘濡傚浘7-29鎵绀,璇峰埄鐢...
绛旓細鏈鐭矾寰勮繛鎺ユ硶锛10+14+12+18=54
绛旓細鏁版嵁缁撴瀯绠绛旈:瀵逛笅鍥鎵绀鐨鏃犲悜甯︽潈鍥,1鍐欏嚭浠栫殑鏁扮粍琛ㄧず娉;2鎸塸rim绠楁硶姹傚叾鏈灏忕敓鎴愭爲,鐢诲嚭鐢熸垚鐨勫叏杩囩▼銆... 鏁版嵁缁撴瀯绠绛旈:瀵逛笅鍥炬墍绀虹殑鏃犲悜甯︽潈鍥,1鍐欏嚭浠栫殑鏁扮粍琛ㄧず娉;2鎸塸rim绠楁硶姹傚叾鏈灏忕敓鎴愭爲,鐢诲嚭鐢熸垚鐨勫叏杩囩▼銆 灞曞紑 鎴戞潵绛 1...
绛旓細甯︽潈鏃犲悜鍥鐨勯偦鎺ョ煩闃垫槸涓绉嶈〃绀哄浘涓《鐐逛箣闂村叧绯荤殑鏁版嵁缁撴瀯銆傚畠鐨勭壒鐐瑰涓嬶細1.瀵圭О鎬э細甯︽潈鏃犲悜鍥剧殑閭绘帴鐭╅樀鏄竴涓瀵圭О鐭╅樀锛屽嵆鐭╅樀鐨勭i琛岀j鍒楃殑鍏冪礌涓庣j琛岀i鍒楃殑鍏冪礌鐩哥瓑銆傝繖鏄洜涓哄湪鏃犲悜鍥句腑锛屽鏋滈《鐐筰涓庨《鐐筳涔嬮棿瀛樺湪涓鏉¤竟锛岄偅涔堥《鐐筳涓庨《鐐筰涔嬮棿涔熶竴瀹氬瓨鍦ㄤ竴鏉¤竟銆2.瀵硅绾垮厓绱犱负0...
