?? wfj.cpp
字號:
#include "stdlib.h" /* For _MAX_PATH definition */
#include "stdio.h"
#include "malloc.h"
#include "conio.h"
#include "ctype.h"
#include "iostream.h"
#define MAX 50
int n,c[100][100];
void prim()
{
int i,j,k,min;
int *lowcost;
int *closest;
int *s;
lowcost=(int*)malloc(sizeof(int)*(n+1));
closest=(int*)malloc(sizeof(int)*(n+1));
s=(int*)malloc(sizeof(int)*(n+1));
s[1]=1;
for(i=2;i<=n;i++)
{
lowcost[i]=c[1][i];
closest[i]=1;
s[i]=0;
}
for(i=1;i<n;i++)
{
min=MAX;
j=1;
for(k=2;k<=n;k++)
if((lowcost[k]<min)&&(!s[k]))
{
min=lowcost[k];
j=k;
}
cout<<"("<<j<<","<<closest[j]<<")"<<" "<<"成本為:";
if(j>closest[j])
{
cout<<c[closest[j]][j];
}
if(j<closest[j])
{
cout<<c[j][closest[j]];
}
cout<<endl;
s[j]=1 ;
for(k=2;k<=n;k++)
if((c[j][k]<lowcost[k])&&(!s[k]))
{
lowcost[k]=c[j][k];
closest[k]=j;
}
}
}
void main()
{
int i,j;
cout<<"**************利用Prim算法得出的最小生成樹的邊如下**************"<<endl;
cout<<"輸入時,如果兩點之間沒有連接邊請輸入一個比所有權值都大的數表示‘無窮大’"<<endl<<endl;
cout<<"請輸入圖中節點的個數:";
cin>>n;
cout<<endl<<endl<<"你輸入的節點個數為:";
cout<<"請輸入的圖中各邊的權值:"<<endl;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
cout<<" 邊("<<i<<","<<j<<")的權值:";
cin>>c[i][j];
}
cout<<endl<<endl<<"**************<<""利用Prim算法得出的最小生成樹的邊如下**************"<<endl;
prim();
getch();
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -