?? algo7-2.cpp
字號:
// algo7-2.cpp 實現算法7.9的程序
#include"c1.h"
typedef int VRType;
typedef char InfoType;
#define MAX_NAME 3 // 頂點字符串的最大長度+1
#define MAX_INFO 20 // 相關信息字符串的最大長度+1
typedef char VertexType[MAX_NAME];
#include"c7-1.h"
#include"bo7-1.cpp"
typedef struct
{ // 記錄從頂點集U到V-U的代價最小的邊的輔助數組定義
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
int minimum(minside SZ,MGraph G)
{ // 求closedge.lowcost的最小正值
int i=0,j,k,min;
while(!SZ[i].lowcost)
i++;
min=SZ[i].lowcost; // 第一個不為0的值
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0)
if(min>SZ[j].lowcost)
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(MGraph G,VertexType u)
{ // 用普里姆算法從第u個頂點出發構造網G的最小生成樹T,輸出T的各條邊。算法7.9
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j) // 輔助數組初始化
{
if(j!=k)
{
strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0; // 初始,U={u}
printf("最小代價生成樹的各條邊為:\n");
for(i=1;i<G.vexnum;++i)
{ // 選擇其余G.vexnum-1個頂點
k=minimum(closedge,G); // 求出T的下一個結點:第K頂點
printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]); // 輸出生成樹的邊
closedge[k].lowcost=0; // 第K頂點并入U集
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
{ // 新頂點并入U集后重新選擇最小邊
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
void main()
{
MGraph G;
CreateAN(G);
MiniSpanTree_PRIM(G,G.vexs[0]);
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -