最小生成树问题源代码
#include
#include
using namespace std;
#define int_max 10000
#define inf 9999
#define max 20
#define MAX 20
#define M 20
typedef struct ArcCell
{
int adj;
char *info;
}ArcCell,AdjMatrix[20][20];
typedef struct
{
char vexs[20];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
int localvex(MGraph G,char v)
{
int i=0;
while(G.vexs[i]!=v)
{++i;}
return i;
}
void ljjzprint(MGraph G)
{ int i,j,n=0; printf("建立的邻接矩阵如下：\n"); printf("\n");
printf(" _____________________________________________\n");
for(i=0;i!=G.vexnum;i++)
{ for(j=0;j!=G.vexnum;j++)
{ if(j==0)printf(" ");
printf("%d",G.arcs[i][j].adj);printf(" ");n++;
if(n==G.vexnum){ printf("\n");n=0;} }
}
printf(" ______________________________________________\n");} int creatMGraph(MGraph &G)
{char v1,v2; int i,j,w;
printf("建立邻接矩阵:\n");
printf("请输入图G顶点（城市）和弧（边）的个数:");
scanf("%d",&G.vexnum); scanf("%d",&G.arcnum); printf("输入所有顶点:");
for(i=0;i>G.vexs[i]; }
for(i=0;i>v1>>v2>>w; i=localvex(G,v1); j=localvex(G,v2);
G.arcs[i][j].adj=w; G.arcs[j][i].adj=w; }
ljjzprint(G);
printf("图G邻接矩阵创建成功！\n");
return G.vexnum;} int visited[max]; int we; typedef struct arcnode
{ int adjvex; struct arcnode *nextarc; char *info; }arcnode;
typedef struct vnode
{ char data; arcnode *firstarc; }vnode,adjlist; typedef struct//图的定义
{ adjlist vertices[max]; int vexnum, arcnum; int kind; }algraph;
int prim(int g[][max],int n) //最小生成树PRIM算法
{
int lowcost[max], prevex[max];
int i,j,k,min;
int sum=0;
for(i=2;i<=n;i++)
{
lowcost[i]=g[1][i];
prevex[i]=1;
}
lowcost[1]=0;
for(i=2;i<=n;i++)
{
min=inf;
k=0;
for(j=2;j<=n;j++)
if((lowcost[j]arcnum,&D->vexnum);
for(i=1;i<=D->vexnum;i++)//初始化图
{
for(j=1;j<=D->vexnum; j++)
{
D->arc[i][j].adj=D->arc[j][i].adj=0;
}
}
for(i=1;i<=D->arcnum;i++)//输入边和权值
{
printf("\n请输入有边的2个顶点");
scanf("%d %d",&n,&m);
while(n<0||n>D->vexnum||m<0||n>D->vexnum)
{
printf("输入的数字不符合要求 请重新输入:");
scanf("%d%d",&n,&m);
}
D->arc[n][m].adj=D->arc[m][n].adj=1;
getchar();
printf("\n请输入%d与%d之间的权值:",n,m);
scanf("%d",&D->arc[n][m].weight);
}
printf("邻接矩阵为:\n");
for(i=1;i<=D->vexnum;i++)
{
for(j=1;j<=D->vexnum;j++)
{
printf("%d ",D->arc[i][j].adj);
}
printf("\n");
}
}
void sort(edge edges[],MGraphA *D)//对权值进行排序
{
int i, j;
for(i=1;iarcnum;i++)
{
for(j=i+1;j<=D->arcnum;j++)
{
if(edges[i].weight>edges[j].weight)
{
Swapn(edges, i, j);
}
}
}
printf("权排序之后的为:\n");
for(i=1;iarcnum;i++)
{
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
void Swapn(edge *edges,int i, int j)//交换权值 以及头和尾
{
int temp;
temp=edges[i].begin;
edges[i].begin=edges[j].begin;
edges[j].begin=temp;
temp=edges[i].end;
edges[i].end=edges[j].end;
edges[j].end=temp;
temp=edges[i].weight;
edges[i].weight=edges[j].weight;
edges[j].weight=temp;
}
void MiniSpanTree(MGraphA *D)//生成最小生成树
{
int i,j,n,m,SUM=0;
int k=1;
int parent[M];
edge edges[M];
for(i=1;ivexnum;i++)
{
for(j=i+1;j<=D->vexnum;j++)
{
if(D->arc[i][j].adj==1)
{
edges[k].begin=i;
edges[k].end=j;
edges[k].weight=D->arc[i][j].weight;
k++;
}
}
}
sort(edges, D);
for(i=1;i<=D->arcnum; i++)
{
parent[i]=0;
}
printf("最小生成树为:\n");
for(i=1;i<=D->arcnum; i++)//核心部分
{
n=Find(parent, edges[i].begin);
m=Find(parent, edges[i].end);
if(n!=m)
{
parent[n]=m;
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);
SUM=SUM+edges[i].weight;
}
}
cout<<"最少生成树的代价:";
cout<0)
{
f=parent[f];
}
return f;
}
void main()
{
algraph gra;
MGraph G;
MGraphA *D;
int i,d,m,g[20][20];
char a='a';
int s;
char y='y';
while(y='y')
{
printf(" …………最小生成树的求法…………\n");
printf(" ____________________________________________\n");
printf(" | 1.建立邻接矩阵(无向图) |\n");
printf(" | 2.用prim算法求最小生成树(无向图) |\n");
printf(" | 3.用kruskal算法求最小生成树 |\n");
printf(" |___________________________________________ |\n");
printf(" 请选择相应的菜单(1-3) :");
cin>>s;
switch(s)
{
case 1:
d=creatMGraph(G);
vnode v;
cout<>y;
if(y=='n')
break;
}
}
本文档为【最小生成树问题源代码】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483