?typedef?int?VRType;
?typedef?char?InfoType;
?#define?MAX_NAME?3?//?頂點字符串的最大長度+1
?#define?MAX_INFO?20?//?相關信息字符串的最大長度+1
?typedef?char?VertexType[MAX_NAME];
?#include“Graph_Matrix.h“
?#include“Graph.h“

?typedef?struct
?{?//?記錄從頂點集U到V-U的代價最小的邊的輔助數(shù)組定義
???VertexType?adjvex;
???VRType?lowcost;
?}minside[MAX_VERTEX_NUM];

?int?minimum（minside?SZMGraph?G）
?{?//?求SZ.lowcost的最小正值，并返回其在SZ中的序號
???int?i=0jkmin;
???while（!SZ[i].lowcost）
?????i++;
???min=SZ[i].lowcost;?//?第一個不為0的值
???k=i;
???for（j=i+1;j?????if（SZ[j].lowcost>0&&min>SZ[j].lowcost）?//?找到新的大于0的最小值
?????{
???????min=SZ[j].lowcost;
???????k=j;
?????}
???return?k;
?}

?void?MiniSpanTree_PRIM（MGraph?GVertexType?u）
?{?//?用普里姆算法從第u個頂點出發(fā)構造網(wǎng)G的最小生成樹T，輸出T的各條邊。
???int?ijkm;
???minside?closedge;
???k=LocateVex（Gu）;
???for（j=0;j???{
?????strcpy（closedge[j].adjvexu）;
?????closedge[j].lowcost=G.arcs[k][j].adj;
???}
???closedge[k].lowcost=0;?//?初始U={u}
???printf（“最小代價生成樹的各條邊為:\n“）;
???for（i=1;i???{?//?選擇其余G.vexnum-1個頂點
?????k=minimum（closedgeG）;?//?求出T的下一個結點：第k頂點
	?m=LocateVex（Gclosedge[k].adjvex）;//獲取第一個頂點在數(shù)組中的位置
?????printf（“（%s-%s）?%d\n“closedge[k].adjvexG.vexs[k]G.arcs[m][k].adj）;?//?輸出生成樹的邊及權值
?????closedge[k].lowcost=0;?//?第k頂點并入U集
?????for（j=0;j???????if（G.arcs[k][j].adj???????{?//?新頂點并入U集后重新選擇最小邊
?????????strcpy（closedge[j].adjvexG.vexs[k]）;
?????????closedge[j].lowcost=G.arcs[k][j].adj;
???????}
???}
?}

?void?main（）
?{
???MGraph?g;
???CreateUDN（g）;?//?構造無向網(wǎng)g
???Display（g）;?//?輸出無向網(wǎng)g
???MiniSpanTree_PRIM（gg.vexs[0]）;?//?用普里姆算法從g的第1個頂點出發(fā)輸出最小生成樹的各條邊
???getchar（）;
???getchar（）;
?}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件??????31744??2009-04-15?21:02??4-tongxin\Debug\tongxin.exe

?????文件?????330792??2009-04-15?21:02??4-tongxin\Debug\tongxin.ilk

?????文件?????519168??2009-04-15?21:02??4-tongxin\Debug\tongxin.pdb

?????文件??????11468??2009-04-15?21:03??4-tongxin\tongxin\Debug\BuildLog.htm

?????文件??????35485??2009-04-15?21:02??4-tongxin\tongxin\Debug\Main.obj

?????文件?????????65??2009-04-15?21:03??4-tongxin\tongxin\Debug\mt.dep

?????文件????????621??2009-04-15?21:02??4-tongxin\tongxin\Debug\tongxin.exe.intermediate.manifest

?????文件?????191488??2009-04-15?21:02??4-tongxin\tongxin\Debug\vc90.idb

?????文件?????217088??2009-04-15?21:02??4-tongxin\tongxin\Debug\vc90.pdb

?????文件???????2265??2009-04-15?21:02??4-tongxin\tongxin\Graph.h

?????文件????????601??2009-04-15?19:09??4-tongxin\tongxin\Graph_Matrix.h

?????文件???????1949??2009-04-15?20:56??4-tongxin\tongxin\Main.cpp

?????文件???????3783??2009-04-15?19:09??4-tongxin\tongxin\tongxin.vcproj

?????文件???????1411??2009-04-15?21:05??4-tongxin\tongxin\tongxin.vcproj.Dave-PC.文刀.user

?????文件????1182720??2009-04-15?21:05??4-tongxin\tongxin.ncb

?????文件????????887??2009-04-15?18:54??4-tongxin\tongxin.sln

????..A..H.?????10752??2009-04-15?21:05??4-tongxin\tongxin.suo

?????文件??????98304??2009-05-13?17:06??4-最小通信網(wǎng).doc

?????目錄??????????0??2009-04-15?23:40??4-tongxin\tongxin\Debug

?????目錄??????????0??2009-04-15?23:40??4-tongxin\Debug

?????目錄??????????0??2009-04-15?23:40??4-tongxin\tongxin

?????目錄??????????0??2009-04-15?23:40??4-tongxin

-----------?---------??----------?-----??----

??????????????2640591????????????????????22