求大佬改错，邻接表那里有错，不会改
//图的基本运算算法#include<stdio.h>
#include<malloc.h>
//图的两种存储结构
#define INF 32767//定义∞
#define MAXV 100//最大顶点个数
typedef char InfoType;//存权值
//以下定义邻接矩阵类型
typedef struct
{
int no; //编号
InfoType info;//顶点其他信息
}VertexType;//顶点类型
typedef struct
{
int edges[MAXV][MAXV];//邻接矩阵数组
int n,e;//n顶点数，e边数
VertexType vexs[MAXV];//存顶点信息及编号
}MatGraph; //完整的图邻接矩阵类型
//以下定义邻接表类型
typedef struct ANode
{
int adjvex;//该边的邻接点编号
struct ANode *nextarc;//指向下一条边的指针
int weight;//该边的相关信息，权值
}ArcNode;//表结点
typedef struct VNode
{
InfoType info;//顶点其他信息
int count;//存放顶点入度，仅用于拓扑序列
ArcNode *firstarc;//指向第一条边
}VNode;//表头结点
typedef struct
{
VNode adjlist[MAXV];//邻接表头结点数组
int n,e;//n顶点数，e边数
}AdjGraph;//完整邻接表类型
void CreatMat(MatGraph &g,int A[MAXV][MAXV],int n,int e)//构造邻接矩阵
{
int i,j;
g.n=n;
g.e=e;
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
g.edges[i][j]=A[i][j];
}
void DispMat(MatGraph g)//显示矩阵
{
int i,j;
for(i=0;i<g.n;i++)
{
for(j=0;j<g.n;j++)
{
if(g.edges[i][j]!=INF)
printf("%5d",g.edges[i][j]);
else
printf("%5s",'∞');
}
printf("\n");
}
}
void CreatAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e)//构造邻接表
{
int i,j;
ArcNode *p;//p当前结点及边相关信息
G=(AdjGraph *)malloc(sizeof(AdjGraph));
for(i=0;i<n;i++)//给邻接表中所有头结点指针域
G->adjlist[i].firstarc=NULL;
for(i=0;i<n;i++)//检查邻接矩阵每个元素
for(j=n-1;j>=0;j--)
if(A[i][j]!=0&&A[i][j]!=INF)//存在一条边
{
p=(ArcNode *)malloc(sizeof(ArcNode));//创建一个结点p
p->adjvex=j;
p->weight=A[i][j];
p->nextarc=G->adjlist[i].firstarc;//头插法插入结点p
G->adjlist[i].firstarc=p;
}
G->n=n;
G->e=e;
}
void DispAdj(AdjGraph *G)//显示邻接表;G头结点数组
{
ArcNode *p;
for(int i=0;i<G->n;i++)
{
p=G->adjlist[i].firstarc;//指向当前结点第一个表结点
printf("%5d:",i);
while(p!=NULL)
{
printf("%5d[%d]→",p->adjvex,p->weight);
p=p->nextarc;
}
printf("∧\n");
}
}
void DestroyAdj(AdjGraph *&G)//销毁图的邻接表
{
ArcNode *pre,*p;//pre当前删除结点，p下一个删除的结点
for(int i=0;i<G->n;i++) //扫描所有的链表
{
pre=G->adjlist[i].firstarc;
if(pre!=NULL)
{
p=pre->nextarc;
while(p!=NULL)
{
free(pre);
pre=p;
p=p->nextarc;
}
free(pre);//删除表结点
}
}
free(G);//删除列表
}
void Prim(MatGraph g,int v)
{
int lowcost[MAXV],min,n=g.n;
int closest[MAXV],i,j,k;
for(i=0;i<n;i++)
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for(i=0;i<n;i++)
{
min=INF;
for(j=0;j<n;j++)//找所有顶点lowcost最小值
if(lowcost[j]!=0&&lowcost[j]<min)
{
min=lowcost[j];
k=j;
}
printf(" 边（%d,%d）权值为：%d \n",closest[k],k,min);
lowcost[k]=0;//标记k已经加入最小生成树顶点集合
for(j=0;j<n;j++)//找新加入k后，所有顶点lowcost是否变得更小
if(g.edges[k][j]!=0&&g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
int main()
{
int v=3;
MatGraph g;
AdjGraph G;
int A[MAXV][MAXV]={
{0,6,1,5,0,0},
{6,0,5,0,3,0},
{1,5,0,5,6,4},
{5,0,5,0,0,2},
{0,3,6,0,0,6},
{0,0,4,2,6,0}};
int n=6,e=10;
CreatMat(g,A,n,e);
printf("图G邻接矩阵为：\n");
DispMat(g);
CreatAdj(G,A,n,e);
printf("图G邻接表为：\n");
DispAdj(G);
Prim(g,v);
return 0;
}
