/*带权无向图的邻接矩阵存储方式*/
#include<iostream>
#include<malloc.h>
#define InfoType int
using namespace std;
const int maxsize=50;
typedef struct
{
int data; //vertex data,顶点编号
InfoType info; //顶点其他信息
}VertexType;
//图的定义
typedef struct
{
int n;//顶点数
int e;//边数
int edges[maxsize][maxsize];//邻接矩阵
VertexType vexs[maxsize];//存放顶点信息
}MatGraph;
//找出v所在vexs数组的下标
int locatevex(MatGraph *G,char v)
{
int k;
for (k=0;k<G->n;k++)
if (G->vexs[k].data==v)
return k;
}
void CreateMatGraph(MatGraph *&G)
{
int i,j,k,w;
char v1,v2;
cout<<"输入图的顶点个数和边的个数："<<endl;
cin>>G->n>>G->e;
cout<<"输入各个顶点的信息："<<endl;
for(k=0;k<G->n;k++)
{
cin>>G->vexs[k].data;
}
//初始化设置邻接矩阵的对角线的值为0，其余部分为无穷大
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
{
if(i==j)
G->edges[i][j]=0;
else
G->edges[i][j]=32767;
}
//找到两顶点的位置，并再矩阵的相应位置赋权值
cout<<"输入两顶点名称和两顶点之间边的权值："<<endl;
for(k=0;k<G->e;k++)
{
cin>>v1>>v2>>w; //顶点名称和权值
i=locatevex(G,v1);
j=locatevex(G,v2); //找顶点序号
G->edges[i][j]=w;
G->edges[j][i]=w;
}
}
void Prim(MatGraph *g,int v)
{
int lowcost[maxsize];
int min;
int closest[maxsize],i,j,k,n;
for(i=0;i<g->n;i++)//给lowcost[]和closest[]置初值
{
lowcost[i]=g->edges[v][i];
closest[i]=v;
}
for(i=1;i<g->n;i++)//输出(n-1)条边
{
min=32767;
for(j=0;j<g->n;j++)//在(V-U)中找出离U最近的顶点k
{
if(lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];
k=j;//k记录最近顶点编号
}
}
cout<<"相邻的两点： "<<closest[k]<<" "<<k<<endl;
cout<<"两点之间边的权值为： "<<min<<endl;
lowcost[k]=0;//标记k已经加入U
cout<<1<<endl;
for(j=0;j<g->n;j++)//修改数组lowcost和closest
{
if(lowcost[j]!=0 && g->edges[k][j]<lowcost[j])
{
lowcost[j]=g->edges[k][j];
closest[j]=k;
}
}
}
}
int main()
{
MatGraph *G;//定义邻接矩阵指针G
G=(MatGraph *)malloc(sizeof(MatGraph));//为指针G分配存储空间
CreateMatGraph(G);
int v;
cout<<"输入起始顶点编号："<<endl;
cin>>v;
Prim(G,v);
return 0;
} 主要问题出现在普里姆算法的中的for循环之中，无法输出相邻的点和两点边的权值
参考输入值
输入图的顶点个数和边的个数：
7 9
输入各个顶点的信息：
0 1 2 3 4 5 6
输入两顶点名称和两顶点之间边的权值：
0 1 28
0 5 10
5 4 25
4 6 24
6 1 14
6 3 18
4 3 22
3 2 12
1 2 16
输入起始顶点编号：
0
一、
int locatevex(MatGraph *G,char v)
{
int k;
for (k=0;k<G->n;k++)
if (G->vexs[k].data==v)
return k;
}
这里的v是char型的。
二、
typedef struct
{
int data; //vertex data,顶点编号
InfoType info; //顶点其他信息
}VertexType;
这里的data是int型的
进行了int==char的操作 实测把int data 换成char data可以运行且样例正确跑过。
因为char值为‘0’的int值为48 并不会等于int 0。