?? priml.cpp
字號:
#include <stdio.h>
#define MAX 1000
#define MAXNode 20
typedef struct
{
int vexnum,arcnum;
int arcs[MAXNode][MAXNode];
}MGraph;//用鄰接矩陣存儲
void CreateMGraph(MGraph *p)
{
int i,j,n,m;
int v1,v2,w;
printf("請輸入頂點個數:");
scanf("%d",&n);
p->vexnum=n;
printf("請輸入邊數:");
scanf("%d",&m);
p->arcnum=m;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
if(i==j)
p->arcs[i][j]=0;
else
p->arcs[i][j]=MAX;//鄰接矩陣初始化
for(i=1;i<=m;i++)
{
printf("請輸入第%d條邊的頂點序號v(0<=v<=%d)及該邊權值:",i,n);
scanf("%d %d %d",&v1,&v2,&w);
if(v1>=0&&v1<n&&v2>=0&&v2<n)
{
p->arcs[v1][v2]=w;
p->arcs[v2][v1]=w;
}//if
}//for
}
int prim(MGraph G,int v)
{//用prim算法從序號為v的頂點出發構造最小生成樹
//并返回權值和
int i,j,k,min,c=0;
int lowcost[MAXNode],closest[MAXNode];
for(i=0;i<G.vexnum;++i)
{//對每一個結點
closest[i]=v;//初值最近點
lowcost[i]=G.arcs[v][i];
}
for(i=0;i<G.vexnum-1;i++)
{
min=MAX;
for(j=0;j<G.vexnum;++j)
//在余下的頂點中找出最近的那個,并用k記下其序號
if(lowcost[j]!=0&&lowcost[j]<min)
{
min=lowcost[j];
k=j;
}
printf("v%d-v%d\t%d\n",closest[k],k,min);
c+=min;
lowcost[k]=0;//將此點歸并
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j]!=0&&G.arcs[k][j]<lowcost[j])
{
lowcost[j]=G.arcs[k][j];
closest[j]=k;
}
}
return c;
}
/*int Kruskal(Graph G)
{//用Kruskal算法從序號為0的頂點出發構造最小生成樹
//并返回權值和
int i,j,min,c=0,k;
for(i=0;i<G.vexnum;i++)
{//對每一個結點
min=MAX;
for(j=0;j<G.vexnum;++j)
{ if(i!=j&&G.arcs[i][j]<min)
min=G.arcs[i][j];
k=j;
}
G.arcs[k][i]=MAX;
printf("v%d-v%d %d\n",i,k,min);
c+=min;
}
return c;
}*/
void Prim()
{
int cost;
MGraph G;
CreateMGraph(&G);
printf("prim得的最小生成樹為:\n");
printf("邊\t 權值\t\n");
cost=prim(G,0);
printf("Cost : %d\n",cost);
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -