数据结构实验六 最小生成树—Prim-Kruskal
#include
#include "stdio.h"
#include "stdlib.h"
#include "cstdlib"//syste()函数需要该头文件；
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MaxInt 32767 //网中表示极大值，即∞,若为无向图，Mxint 0；
//#define INFINITY 0//图中表示初始值0；网中表示极大值，即∞.在无向图中不存在权，用这个单词比Maxint含义好
#define MVNum 100 //最大顶点数
#define MENum 20 //最大边数
//00定义 点 边 图网
typedef char VerTexType; //假设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型，若为无向图，ArcType->EdgeType
typedef struct{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //图的当前点数和边数
}AMGraph;
//01 定位Locate the vertex you need
int LocateVex(AMGraph G,char ch)
{
int i=0;
for(i=0; i
{
if(G.vexs[i]==ch)
break;
}
if(i>=G.vexnum) //如果超过顶点数量了，返回-1
return -1;
return i; //return the index of the vertex you are looking
}
//02 打印 顶点（一维数组） 边（二维数组）
Status PrintAMGraphVex(AMGraph G)//打印顶点，一维数组
{
int i;
printf("你输入的顶点是：");
for(i=0;i
{
printf("%c\t",G.vexs[i]);
}
printf("\n");
return OK;
}
Status PrintAMGraphArc(AMGraph G)//打印邻接矩阵，二维数组
{
int i,j;
cout<<"当前邻接矩阵是："<
for(i=0;i
{
for(j=0;j
{
printf("%d\t",G.arcs[i][j]);
}
printf("\n\n\n");
}
return OK;
}
//03 建立一个无方向网图的邻接矩阵表示
Status CreateGraph(AMGraph &G)
{
int i,j,k,w;
char v1,v2;
printf("Input the number of vertex and arc:\n");
cin>>G.vexnum>>G.arcnum;
printf("The number is %d and %d.\n",G.vexnum,G.arcnum);//验证输入内容
//initialize vertex arcs;
printf("Input %d vertex: ",G.vexnum);
for(i=0;i
cin>>G.vexs[i];
PrintAMGraphVex(G);//验证输入的顶点
for(i=0;i
for(j=0;j
{
// if(i!=j)
G.arcs[i][j]=MaxInt;//无穷
// else
// G.arcs[i][j]=0;
}
PrintAMGraphArc(G);//验证输入的边
for (k = 0; k < G.arcnum; ++k)
{
printf("input the i and j of (Vi,Vj), and the weight:\n"); //一条边的两个结点，和这条边的权重,无向图权值输入1；也可以前面声明为1.
cin>>v1>>v2>>w;
//cout<<"你输入的v1 v2 w :"<
i=LocateVex(G,v1);
j=LocateVex(G,v2);
//cout<<"i:"<
//cout<<"j:"<
if(i==-1 || j==-1)
{
return ERROR;
}
G.arcs[i][j]=w;
G.arcs[j][i]=G.arcs[i][j];//如果是有向网，可以w1 w2
//cout<<"G.arcs[i][j] :"<
}
return OK;
}
//普利姆算法
struct Node //需要用一个结构体来记录产生的最小的生成树
{
VerTexType adjvex;//最小边在U的那个顶点
ArcType lowcost;//最小边上的权值
}closedge[MVNum];
void MiniSpanTree_Prim(AMGraph G,VerTexType u)
{
int i,j,k;
k=LocateVex(G,u);
//初始化closedge
for(j=0;j
{
if(j!=k)//i!=k是因为结点本身和结点本身不能产生关系
{
closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j];
}
}
closedge[k].lowcost=0;//初始，U={u};
VerTexType u0,v0;
int min,sum=0;
printf("最小生成树：\n");
for(i=1;i
{
min=MaxInt;//k=Min(closedge)
for(int j=0;j
{
if(closedge[j].lowcost>0)
{
if(closedge[j].lowcost
{
k=j;
min=closedge[j].lowcost;
}
}
}
u0=closedge[k].adjvex;
v0=G.vexs[k];
cout<
sum+=closedge[k].lowcost;
closedge[k].lowcost=0;//还要修改closedge数组
for(j=0;j
{
if(G.arcs[k][j]
{
closedge[j].lowcost=G.arcs[k][j];
closedge[j].adjvex=G.vexs[k];
}
}
}
printf("最小路径长度为：%d\n",sum);
}
//Kruskal算法
struct EdgeNode //需要用一个结构体来记录产生的最小的生成树
{
VerTexType Head;//边的始点
VerTexType Tail;//边的终点
ArcType lowcost;//边的权值
}Edge[2*MENum];
Status Sort(EdgeNode a[])//从小到大
{
int i,j;
EdgeNode temp;
for(i=0;i<2*MENum;i++)
for(j=0;j<2*MENum;j++)
if(a[j].lowcost>a[j+1].lowcost)
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
return OK;
}
void MiniSpanTree_Kruskal(AMGraph G)
{
int i,j,v1,v2,vs1,vs2,k=0,Vexset[MVNum];//需要用到并查集，看是否选出的边的两个顶点是否已经归并，避免形成回路.
for(i=0;i
Vexset[i]=i;//初始化,各自是只有一个结点的连通分量，避免回路
//初始化Edge
for(i=0;i
for(j=0;j
if(G.arcs[i][j]
{
Edge[k].Head=G.vexs[i];
Edge[k].Tail=G.vexs[j];
Edge[k].lowcost=G.arcs[i][j];
k++;
}
for(k;k<=2*MENum;k++)//开辟数组只能定值，空间用不完，后面要填一个大值，因为sort从小到大，而数组默认0
{
Edge[k].lowcost=MaxInt;
}
//从小到大排序
Sort(Edge);
cout<<"Edge[]数组是：\n";
for(i=0;i<2*G.arcnum;i++)
cout<
cout<<"最小生成树：\n";
int sum=0;
for(i=0;i<2*G.arcnum;i++)
{
v1=LocateVex(G,Edge[i].Head);
v2=LocateVex(G,Edge[i].Tail);
vs1=Vexset[v1];
vs2=Vexset[v2];
if(vs1!=vs2)
{
cout<
sum+=Edge[i].lowcost;
for(j=0;j
{
if(Vexset[j]==vs2)
Vexset[j]=vs1;
}
}
}
printf("\n最短路径长度为：%d\n",sum);
}
Status main()
{
AMGraph G;
CreateGraph(G);
PrintAMGraphArc(G);
MiniSpanTree_Prim(G,'A');
cout<<"Kruskal:\n";
MiniSpanTree_Kruskal(G);
system("pause");
return OK;
}